# Proving inequality by induction only

Suppose $a_1,\dots,a_n$ are real positive numbers s.t. $\prod_{i=1}^n a_i=1$. My book claims that by induction only (i.e. the use of AM-GM is forbidden), one can prove that $$\sum a_i\ge n$$ and that equiality exists if and only if $\forall i,a_i=1$. I tried to prove it:

for $n=2,$ denote $a_1=a,a_2=\frac 1 a$ then: $$0\le \frac{(a-1)^2}{a}=a+\frac{1}{a}-2\Rightarrow a_1+a_2\ge 2.$$

Now we need to prove it for $n+1$. Denote by $b_n=a_na_{n+1}$, By hypothesis $$a_1\cdots a_{n-1} b_n=1\Rightarrow a_1+\dots a_{n-1}+b_n\ge n$$ which means $$a_1+\dots+a_{n-1}+a_n +a_{n+1} \ge n-b_n+a_n+a_{n+1}.$$ That means I need to prove $$a_n+a_{n+1}-a_na_{n+1}\ge 1$$ but I don't know how.

How can I complete the proof?

• Just a note, writing $0\leq (a-b)^2$ (which is in principle the $n=2$ step) is (no surprise) equivalent to $ab\leq\frac{1}{2}(a^2+b^2)$, i.e. the arithmetic-geometric inequality. I guess the important thing here is not to use arithmetic-geometric inequality directly in the general step. – mickep Sep 18 '15 at 4:49
• When proving for $n+1$, first do the following: because the product of the variables is $1$, there must exist at least one variable $\ge 1$ and one $\le 1$ (otherwise the variables will be either all > 1 or all < 1 and thus their product cannot be 1). Without loss of generality (since the role of the variables are the same), suppose that $a_n \ge 1$ and $a_{n+1}\le 1$. Then we have $(1-a_n)(1-a_{n+1})\le 0$, equivalent to $a_n+a_{n+1}- a_na_{n+1}\ge 1$. Now applying the inequality for $n$ numbers we have...etc... – Khue Sep 18 '15 at 9:48

The inequality you need to prove (I think you should change the $n-1$ to $n+1$ if you follow what you have on the previous line), $$a_n+a_{n+1}-a_na_{n+1}\geq 1$$ is not in general true. Take $a_n=a_{n+1}=2$ (which is perfectly valid). This gives zero in the left-hand side.

So, maybe what you can do, is to assume that you, in your product $b_n=a_na_{n+1}$ choose the elements $a_n$ and $a_{n+1}$ that has a certain property?

• Why such elements exist? – Flaring Joe Sep 18 '15 at 5:01
• Say that you, among the numbers $a_1$, $\cdots$, $a_{n+1}$ with product one were unlucky to have $a_n=2$ and $a_ {n+1}=2$. Then, you must also have other elements that are strictly less than one. The only thing I meant in my answer, is that maybe you can find $a_j$ and $a_k$ in your list such that $a_j+a_k-a_ja_k\geq 1$. Do you agree that it would be sufficient? – mickep Sep 18 '15 at 5:05
• My answer shows that you do not need to assume any of the $a_i$ have any special relation to $1$. – marty cohen Sep 18 '15 at 5:21
• That'd be sufficient but I'm not sure how can I pick these $a_j,a_k$. I assume they have to be both $\le 1$ but how to continue? – Flaring Joe Sep 18 '15 at 5:21
• @mickep Albeit it's trivial but can you please explain why one doesn't have to assume any relation of $a_i$ to 1(in sake of completeness)? – Alan Watts Sep 18 '15 at 5:56

$$a_n+a_{n+1}-a_na_{n+1}\ge 1 \Leftrightarrow 1 - a_n -a_{n+1} + a_na_{n+1} \le 0.$$

Factorize the LHS and you will see which $a_n$ and $a_{n+1}$ you should pick.

What we want to show is that $\prod_{i=1}^n a_i=1 \implies \sum a_i\ge n$.

This is certainly true for $n=1$.

Suppose it is true for $n$.

Suppose we have $\prod_{i=1}^{n+1} a_i=1$. We want to show that $\sum_{i=1}^{n+1} a_i\ge n+1$.

As a first try, let's look at $\prod_{i=1}^{n} a_i$. If $A =(\prod_{i=1}^{n} a_i)^{1/n}$ and $b_i =a_i/A$, then $\prod_{i=1}^{n} b_i = 1$, so $\sum_{i=1}^{n} b_i \ge n$, or $\sum_{i=1}^{n} a_i \ge An$. Therefore $\sum_{i=1}^{n+1} a_i \ge An+a_{n+1}$.

If we can show that $An+a_{n+1} \ge n+1$, we are done.

This is the same as $\frac{An+a_{n+1}}{n+1} \ge 1$. But $1 =\prod_{i=1}^{n+1} a_i =a_{n+1}\prod_{i=1}^{n} a_i =a_{n+1}A^n$, so this is the same as $\frac{An+a_{n+1}}{n+1} \ge a_{n+1}A^n$ or $An+a_{n+1} \ge (n+1)a_{n+1}A^n$ or $An+1/A^n \ge (n+1)a_{n+1}A^n$

By the AM-GM means inequality, since $nA$ is $n$ copies of $A$,

$\begin{array}\\ \frac{ An+a_{n+1}}{n+1} &\ge \sqrt[n]{A^n a_{n+1}}\\ &= \sqrt[n]{(\prod_{i=1}^n a_i) a_{n+1}}\\ &= \sqrt[n]{\prod_{i=1}^{n+1} a_i}\\ &= 1\\ \end{array}$

and, to my pleasant surprise, we are done.

We are not allowed to use the AM-GM inequality. However, I will now show, based on some earlier work of my own, that this particular use on the AM-GM inequality, in which all but one of the values are equal, is a consequence of Bernoulli's inequality.

Bernoulli's inequality, which is easily proved by induction, states that $(1+x)^m \ge 1+mx$ if $x \ge 0$ and $m$ is a positive integer with equality if and only if $m = 1$ or $x = 0$.

Therefore $(1+\frac{v/u-1}{m})^m \ge 1+m\frac{v/u-1}{m} = \frac{v}{u}$ with equality only if $m=1$ or $v/u-1 = 0$, which is the same as $v = u$. Multiplying by $u^m$, this becomes

$\begin{array}\\ u^{m-1}v &\le u^m(1+\frac{v/u-1}{m})^m \\ &= (u+\frac{v-u}{m})^m \\ &= (\frac{v+(m-1)u}{m})^m \\ \text{or}\\ (u^{m-1}v)^{1/m} &\le \frac{v+(m-1)u}{m}\\ \end{array}$

But this is just the AM-GM inequality with all but one of the values equal!

Therefore, this use of the AM-GM inequality is OK to use, since it is a consequence of Bernoulli's inequality, not the full AM-GM inequality.

If there is equality, then $A = a_{n+1}$. Since $1 =A^n a_{n+1}$, $1 = a^{n+1}_{n+1}$, so $a_{n+1} = 1$. This implies that there is equality for $n$, so that $a_n = 1$. This allows us to work our way back down in an odd kind of inverse induction to show that equality at any step shows that at that step and all preceding steps $a_i = 1$.
• That's the case of equality in the AM-GM inequality - all the terms are equal and they consist of $n$ $A$s and one $a_{n+1}$. – marty cohen Sep 18 '15 at 7:09