Help with Lemma for proof of AM-GM inequality

[CGandC]

Summary:: x

Hey, I'm learning calculus and had to prove the following Lemma which is used to prove AM-GM inequality, I had tried to prove it on my own and it is quite different from what is written in my lecture notes.
I have a feeling that my proof of the Lemma is incorrect, but I just don't understand why, can anyone please help? Thanks for any assistance in advance.

Lemma:
If $a_1,a_2,...,a_n$ are real and positive numbers satisfying $a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_n = 1$ .
Then prove that $\sum_{k=1}^n a_k \geq n$ , for any natural number $n$ .

My proof:
Let $n$ be arbitrary natural number. Let $a_1,a_2,...,a_n$ be real and positive numbers. I'll prove by induction on $n$.

Base case: $n=1$ the Lemma obviously follows.
Induction step: Suppose that $a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_n = 1$ implies $\sum_{k=1}^n a_k \geq n$.
So we'll prove that $a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n+1} = 1$ implies $\sum_{k=1}^{n+1} a_k \geq n+1$.
Suppose $a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n+1} = 1$.
Without loss of generality, assume $a_n \leq 1$ and $a_{n+1} \geq 1$.
it follows that:
$a_1 + a_2 + ... + a_n + a_{n+1} = \sum_{k=1}^n a_k + a_{n+1}$
using the assumption $\sum_{k=1}^n a_k \geq n$ and $a_{n+1} \geq 1$ then $\sum_{k=1}^n a_k +a_{n+1} \geq n+1$ so it follows that $a_1 + a_2 + ... + a_n + a_{n+1} = \sum_{k=1}^n a_k + a_{n+1} \geq n+1$. QED

Proof from notes:
Base case: $n=1$ the Lemma obviously follows.
Induction step: Suppose that $a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_n = 1$ implies $\sum_{k=1}^n a_k \geq n$.
So we'll prove that $a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n+1} = 1$ implies $\sum_{k=1}^{n+1} a_k \geq n+1$.
Suppose $a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n+1} = 1$.
Without loss of generality, assume $a_n \leq 1$ and $a_{n+1} \geq 1$.
it follows that:
$a_1 + a_2 + ... + a_n + a_{n+1} = a_1 + a_2 + ... + a_{n-1} + a_n \cdot a_{n+1} + ( a_n + a_{n+1} - a_n \cdot a_{n+1} ) \geq n + ( a_n + a_{n+1} - a_n \cdot a_{n+1} )$
It is left to prove that $a_n + a_{n+1} - a_n \cdot a_{n+1} ) \geq 1$:
$a_n + a_{n+1} - a_n \cdot a_{n+1} = a_{n+1}(1-a_n) - (1-a_n) = ( a_{n+1} -1 )( 1 - a_n ) \geq 0$ . QED.

 

[fresh_42]

Your mistake is the following:
You didn't use that the product equals $1$. That is, you cannot assume $\sum_{k=1}^{n}a_n > n$ since $a_1\cdot\ldots\cdot a_n \neq 1$

In the second version, the induction hypothesis is used on the set $\{a_1,.\ldots,a_{n-1},(a_n\cdot a_{n+1})\}$ which are $n$ numbers which multiply to $1$. You do not have this condition for your choice of $a_k$.

 

[CGandC]

Thanks. So please tell me if I understood:
1.
In my induction step I first assumed the implication:
$a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n} = 1 \Rightarrow \sum_{k=1}^{n} a_k \geq n$.
However, just because I assumed the implication statement is true, that doesn't mean the hypothesis part is true:
$a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n} = 1$

Am I correct?

2. Further in my induction step, I assumed:
$a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n+1} = 1$.
And this assumption isn't the hypothesis part of the following implication :
$a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n} = 1 \Rightarrow \sum_{k=1}^{n} a_k \geq n$.
Therefore I cannot deduce anything yet from this implication other than that I assumed it is true.

Am I correct?

3. I didn't fully understand why $$ \{a_1,.\ldots,a_{n-1},(a_n\cdot a_{n+1})\} $$ satisfies the induction hypothesis ( the implication ). Can you please elaborate?

 

[fresh_42]

Thanks. So please tell me if I understood:
1.
In my induction step I first assumed the implication:
$a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n} = 1 \Rightarrow \sum_{k=1}^{n} a_k \geq n$.
However, just because I assumed the implication statement is true, that doesn't mean the hypothesis part is true:
$a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n} = 1$

Am I correct?

No. It is true per assumption: If you have $n$ numbers which multiply to $1$, then their sum is at least $n$. Your fault was, that you do not have these $n$ numbers. We have $a_1\cdot\ldots\cdot a_{n+1}=1$. If you drop one factor, this is no longer true. And as it is not true, you cannot use the induction hypothesis. The IF THEN doesn't apply anymore, since the IF is destroyed.

2. Further in my induction step, I assumed:
$a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n+1} = 1$.
And this assumption isn't the hypothesis part of the following implication :
$a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n} = 1 \Rightarrow \sum_{k=1}^{n} a_k \geq n$.
Therefore I cannot deduce anything yet from this implication other than that I assumed it is true.

Am I correct?

No. You said that $a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n+1} = 1$, but you did not use it. The lecture note used it with $a_1\mapsto a_1,\ldots, a_{n_1}\mapsto a_{n-1},a_n\mapsto (a_n\cdot a_{n+1})$. You were confused by all the same names $a_k$ in various situations. It wold have been better to build the Lemma like this:

Lemma: If $x_1,\ldots, x_n$ are positive real numbers such that $x_1\cdot\ldots\cdot x_n=1$, then $x_1+\ldots+x_n \geq n.$
Proof: $n=1:$ Given $a_1>0$ such that $a_1=1$, then $a_1\geq 1$.
Now assume the statement for $n$.
Given $a_1,\ldots,a_{n+1}>0$ such that $a_1\cdot\ldots\cdot a_{n+1}=1$, we must show that $a_1+\ldots+a_n+a_{n+1}\geq n+1$.

The induction hypothesis says, that it is true for any $n$ numbers $x_1,\ldots,x_n$ whose product equals $1$. Not for any arbitrary numbers $a_1,\ldots,a_n$.

Now you said: $a_1+ \ldots + a_n \geq n$ but this is only true if $a_1\cdot\ldots\cdot a_n=1$, which we cannot know. This would only be true for $a_{n+1}=1$, since all we know is $a_1\cdot\ldots\cdot a_{n+1}=1$. You cannot say that any $n$ numbers can be chosen. The condition that their product equals $1$ is necessary.

The lecture note said: Set $x_1:=a_1,\ldots,x_{n-1}:=a_{n-1},x_n:=a_na_{n+1}$ so their product of $n$ numbers $x_1\cdot\ldots\cdot x_n=1$. This way we can apply the induction hypothesis.

3. I didn't fully understand why $$ \{a_1,.\ldots,a_{n-1},(a_n\cdot a_{n+1})\} $$ satisfies the induction hypothesis ( the implication ). Can you please elaborate?

Multiply the $x_k$ as set above.

The confusion comes in because the variable names in the statement $S(a_k;n)$ are the same as in the proof. But we have different roles, so they better had different names. Better to use e.g. $x_k$ in the general statement $S(x_k;n)$, and $a_k$ only for an arbitrary but given set of numbers in the proof. This way you would had been forced to apply the general statement to your set of numbers by mapping the $a_k$ into the staement.

 

[CGandC]

Now it makes more sense.
So the by looking at the induction assumption. The hypothesis part of the implication:
$a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n} = 1 \Rightarrow \sum_{k=1}^{n} a_k \geq n$
tells me " Product over $n$ numbers that satisify being equal to 1 ", I have confused between these numbers with the numbers in the following assumption:
$a_1 \cdot a_2 \cdot \cdot \cdot \cdot a_{n+1} = 1$
these numbers aren't necessarily the same as those in the induction hypothesis and that doesn't even interest us, what interests us is if we can form sum of $n$ numbers in the induction step which will satisfy the induction assumption above ( which is: the multiplication of these $n$ numbers is equal to 1 ).

So, looking at the Proof from notes:
$a_1 + a_2 + ... + a_n + a_{n+1} = a_1 + a_2 + ... + a_{n-1} + a_n \cdot a_{n+1} + ( a_n + a_{n+1} - a_n \cdot a_{n+1} ) = \sum_{k=1}^{n} x_k + ( a_n + a_{n+1} - a_n \cdot a_{n+1} )$
Where $x_1:=a_1,\ldots,x_{n-1}:=a_{n-1},x_n:=a_na_{n+1}$
So it follows that:
$\sum_{k=1}^{n} x_k + ( a_n + a_{n+1} - a_n \cdot a_{n+1} ) \geq n + ( a_n + a_{n+1} - a_n \cdot a_{n+1} )$

 

[CGandC]

I'm just curious, I kinda had a difficulty writing the lemma in logic syntax because of the " for any n numbers $x_1,\ldots,x_n$ " . What is the logical form of this lemma?

My attempt:
$\forall n \in {\bf{N}} \forall x_1 \in {\bf{R}} \forall x_2 \in {\bf{R}} ...\forall x_n \in {\bf{R}} ( ( x_1,x_2,...,x_n > 0 \land x_1 \cdot \cdot \cdot x_n = 1 ) \Rightarrow x_1 + ... + x_n \geq n )$

 

[fresh_42]

This is correct. However, outside logic courses or books, people shorten that expression, e.g. to
$$\forall n\in \mathbb{N}\, \forall x_k\in \mathbb{R}_{>0}\,(k=1,\ldots,n)\, : \,\prod_{k=1}^nx_k =1\Longrightarrow \sum_{k=1}^nx_k\geq n$$
or even shorter by language:
For all positive real numbers $x_1,\ldots,x_k$ holds: $\prod_{k=1}^nx_k =1\Longrightarrow \sum_{k=1}^nx_k\geq n$

I think in logic you even have to put in more parentheses:
$$(\forall n\in \mathbb{N})(\forall k \in \{1,2,\ldots,n\})(\forall x_k\in \{r\in \mathbb{R}\, : \,r>0\})\, : \, \prod_{k=1}^nx_k =1\Longrightarrow \sum_{k=1}^nx_k\geq n$$