# Help with Lemma for proof of AM-GM inequality

• Simple Induction
• CGandC
In summary: 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 \
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.

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##.

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?

CGandC said:
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} )
##

fresh_42
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 )##

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$$

CGandC

## 1. What is the AM-GM inequality?

The AM-GM inequality is a fundamental inequality in mathematics that states that the arithmetic mean of a set of non-negative numbers is always greater than or equal to the geometric mean of the same set of numbers.

## 2. How is the AM-GM inequality used in mathematical proofs?

The AM-GM inequality is often used in mathematical proofs to show that a certain quantity or expression is always greater than or equal to another quantity or expression. It is also used to prove other inequalities and to solve optimization problems.

## 3. What is a lemma in mathematics?

In mathematics, a lemma is a small, self-contained theorem that is used as a stepping stone in the proof of a larger theorem. It is often used to prove more complex theorems or to simplify the proof of a larger theorem.

## 4. How is a lemma used in the proof of the AM-GM inequality?

In the proof of the AM-GM inequality, a lemma is used to show that the arithmetic mean of a set of non-negative numbers is always greater than or equal to the geometric mean of the same set of numbers. This lemma is then used as a key step in the overall proof of the AM-GM inequality.

## 5. Are there any other important inequalities related to the AM-GM inequality?

Yes, there are several other important inequalities related to the AM-GM inequality, such as the Cauchy-Schwarz inequality, the Hölder's inequality, and the Minkowski's inequality. These inequalities are often used in conjunction with the AM-GM inequality to prove more complex mathematical statements.

• Math Proof Training and Practice
Replies
8
Views
1K
• Math Proof Training and Practice
Replies
10
Views
1K
• Math Proof Training and Practice
Replies
61
Views
6K
• Calculus and Beyond Homework Help
Replies
7
Views
369
• Calculus and Beyond Homework Help
Replies
11
Views
1K
• Math Proof Training and Practice
Replies
8
Views
1K
• Linear and Abstract Algebra
Replies
10
Views
2K
• General Math
Replies
1
Views
895
• Topology and Analysis
Replies
1
Views
851
• Calculus
Replies
1
Views
1K