# Invalid induction proof?

Prove the following using mathematical induction. If $a_{1}, a_{1}, ... , a_{n}$ are positive real numbers such that if $$a_{1}a_{2}...a_{n} = 1$$ then $$a_{1}+a_{2}+ ... + a_{n} \geq n$$ My proof: Basis case obvious. In the induction step I assume that $a_{1}a_{2}...a_{k} = 1$ and that $a_{1}+a_{2}+...+a_{k} \geq k$. Let $a_{k+1}$ be such that $a_{1}a_{12}...a_{k+1} = 1$. (this is not valid??) Then it follows that $a_{k+1} = 1$, and thus $$a_{1}+a_{1}+...+a_{k+1 \geq } k +a_{k+1} = k+1$$

-
By the way, there's an "if" too many. – alex Mar 4 '14 at 10:09
Since your induction step implies (as you note) that $a_{k+1}=1$, and since it is manifestly not the case that $a_{k+1}$ has to be $1$, I'd say it's pretty clear that what you've done is not valid. – Gerry Myerson Mar 4 '14 at 10:09
Must induction be used? – Hawk Mar 4 '14 at 10:10
This is a disguised version of the arithmetic mean/geometric mean inequality. – vonbrand Mar 4 '14 at 10:14
@vonbrand exactly...I was intending to do that only. – Hawk Mar 4 '14 at 10:15

The statement that you are proving with induction is $$\forall n \in {\mathbb N} \forall a_1, \dots, a_n \in {\mathbb R}_+. a_1 a_2 \dots a_n = 1 \rightarrow a_1 + a_2 + \dots + a_n \geq n.$$ So the induction hypothesis is that $\forall a_1,\dots,a_n \in {\mathbb R}_+.a_1 a_2 \dots a_n = 1 \rightarrow a_1 + a_2 + \dots + a_n \geq n$ (i.e., quantified over all $a_i$, not just for particular $a_i$). You then take arbitrary $b_1, \dots, b_{n+1} \in {\mathbb R}_+$ with $b_1 b_2 \dots b_{n+1} = 1$ and try to deduce that $b_1 + b_2 + \dots + b_{n+1} \geq n+1$. In the process, you'll have to come up with some clever $a_1, \dots, a_n$ and use the induction hypothesis.

-
This is just a statement about induction, not really an answer. Compare with answer from Ishfaaq. – Tom Collinge Mar 4 '14 at 12:01
@TomCollinge Maybe I should have been more explicit about it, but the actual mistake in the reasoning from the OP is an erroneous induction hypothesis. And, indeed, I don't prove the statement for the OP; instead, I hope that by fixing his induction hypothesis, he'll be able to continue himself with the reasoning. – Magdiragdag Mar 4 '14 at 12:17
Ok, here is what I have come up with based on your fix of induction hypothesis and hint. If $b_{1}b_{2}...b_{n+1} = 1$, then $a_{1}...a_{n}b_{1}b_{2}...b_{n+1} = 1$. Thus by our assumption $a_{1} + a_{2} + ... + a_{n} \geq n$, it follows that $a_{1} + a_{2} + ... + a_{n} + b_{1}b_{2}...b_{n+1} \geq n + b_{1}b_{2}...b_{n+1}$ implies $a_{1} + a_{2} + ... + a_{n} + b_{1}b_{2}...b_{n+1} \geq n + 1$ where $a_{n+1} = b_{1}b_{2}...b_{n+1}$. – user29163 Mar 6 '14 at 16:15
But this does not look right, since our choice of $a_{1}$ must be arbitrarily. But then again it is, because $b_{1}...b_{n+1}$ is arbitrarily. – user29163 Mar 6 '14 at 16:21
No, in the induction step, after assuming the induction hypothesis, start with arbitrary $b_1, \dots, b_{n+1}$ with $b_1\dots b_{n+1} = 1$. Now define clever $a_1, \dots, a_n$ in terms of the $b_i$; the other answers should give you a hint what $a_i$ to pick. From your definition of the $a_i$, it should follow that $a_1\dots a_n = 1$ and then, by induction hypothesis $a_1 + \dots + a_n \geq n$. Then it should follow, using *your definition of these $a_i$, then $b_1 + \dots + b_{n+1} \geq n+1$. – Magdiragdag Mar 6 '14 at 18:30

I think it's been established by other answers that there was a logical error in your proof. I hope you have rectified it so I'm not going to add to that.

Here is my attempt. Not entirely sure of its validity though.

Suppose $a_1 = 1$ for some $a_1 \in \Bbb R \implies a_1 \ge 1$ and hence the result is true for $n = 1$

Assume the result is true for every $k \lt n$. Then whenever $k \lt n,$

$$a_1a_2...a_k = 1 \implies a_1 + a_2 + ... + a_k \ge k \;\; \text {for all a_i \in \Bbb R}$$

Now we suppose $a_1a_2...a_n = 1$ and try to prove that $a_1 + a_2 + .. + a_n \ge n$

Suppose $a_1a_2..a_{n-1}a_n = 1 \implies a_1a_2..(a_{n-1}a_n) = 1$ which is actually a product of $n -1$ real numbers which is equal to $1$. Our induction hypothesis applies and we have that $$a_1 + a_2 + ... + (a_{n-1}a_n) \ge n - 1 ---- (1)$$

Now as long as $n \gt 1$ we should be able to pick $a_{n-1}$ and $a_n$ (without loss of generality) such that $a_{n-1} \ge 1$ and $a_n \le 1$ because otherwise every $a_i \gt 1$ or every $a_i \lt 1$ leading to a contradiction. For these pairs,

$$(a_{n-1} - 1)( a_n - 1 ) \le 0 \implies a_{n-1} + a_n - 1 \ge a_{n-1}a_n$$

Combining this with inequality $(1)$ we have, $$a_1 + a_2 + ... + a_{n - 1} + a_n - 1 \ge n - 1 \implies a_1 + a_2 + ... + a_{n - 1} + a_n \ge n$$

Q.E.D.

Bear in my mind I'm very much an amateur. Please let me know if there is an issue with my proof. Especially with the choice of $a_{n - 1}$ and $a_n$

-
Good analysis, uses "strong induction". As a matter of detail, still need to establish truth for n = 1 as analysis relies on existence of An−1. For n = 1, An = 1 so sum = 1. – Tom Collinge Mar 4 '14 at 11:57
@Tom Collinge: Right you are. But OP said the case for $n = 1$ was obvious to him/her so I omitted it. And this is for my benefit - what do you mean "strong induction"? – Ishfaaq Mar 4 '14 at 12:39
@Tom Collinge: Just googled it. Got it. Although I assumed the "strong" hypothesis what I actually have ended up "using" is weak induction I believe. – Ishfaaq Mar 4 '14 at 12:41
Thanks, I will try to verify the validity myself. – user29163 Mar 6 '14 at 16:10

By AM-GM inequality for $n$ terms,

$$\dfrac{a_1+a_2+a_3+\ldots+a_n}{n}\ge \sqrt[n]{a_1a_2\ldots a_n}$$
It is now given that $a_1a_2\ldots a_n=1$
So, we get, $a_1+a_2+\ldots+a_n\ge n$.
This completes our proof.

-
@DonAntonio I would do it like this. But, I do not realise how is this induction? – Hawk Mar 4 '14 at 12:35

That's not the right way to use induction. Your argument only proved the case when every $a_k=1$. Surly you can give a proof based on induction for this proposition, but it would be easier to apply the Inequality of arithmetic and geometric means directly.

-

By induction it can be proved like this:

Let $a_{1},\dots,a_{n+1}>0$ with $a_{1}\times\cdots\times a_{n}\times a_{n+1}=1$.

Then $\left(ca_{1}\right)\times\cdots\times\left(ca_{n}\right)=1$ for $c=a_{n+1}^{\frac{1}{n}}$ and by induction $\left(ca_{1}\right)+\cdots+\left(ca_{n}\right)\geq n$ leading to $a_{1}+\cdots+a_{n}+a_{n+1}\geq na_{n+1}^{-\frac{1}{n}}+a_{n+1}$.

So if we can prove that $nx+x^{-n}\geq n+1$ for each $x>0$ (here $x=a_{n+1}^{-\frac{1}{n}}$) then we are ready.

For $f\left(x\right)=nx+x^{-n}$ we find $f'\left(x\right)=n\left(1-x^{-n-1}\right)$.

Then $f'\left(x\right)<0$ if $0<x<1$, $f'\left(1\right)=0$ and $f'\left(x\right)>0$ if $x>1$ showing that a minimum is achieved at $x=1$.

This justifies the conclusion that $nx+x^{-n}\geq f\left(1\right)=n+1$ for each $x>0$.

-