The AM-GM Inequality - Sohrab Proposition 2.1.25 ....

[Math Amateur]

I am reading Houshang H. Sohrab's book: "Basic Real Analysis" (Second Edition).

I am focused on Chapter 2: Sequences and Series of Real Numbers ... ...

I need help with the proof of Proposition 2.1.25 ...

Proposition 2.1.25 reads as follows:View attachment 7071
View attachment 7072In the above proof, Sohrab appears to be using mathematical induction ... BUT ... he proves the inequality for \(\displaystyle n= 2\), but then, in the inductive step, instead of assuming the inequality is true for \(\displaystyle n\) and then proving it is true for \(\displaystyle n+1\) ... Sohrab assumes the inequality is true for \(\displaystyle n = 2^m\) and then proceeds to prove it true for \(\displaystyle 2n = 2^{ m+1}\) ... then finishes the proof by picking an \(\displaystyle m\) such that \(\displaystyle n \lt 2^m\) and establishing the inequality ...
My questions are as follows:

What is the valid proof process here ... ?

How does the proof process fit with the usual mathematical induction strategy ...Peter

 

[Opalg]

What is the valid proof process here ... ?

How does the proof process fit with the usual mathematical induction strategy ...

The proof consists of two separate parts. The first part proves by induction on $m$ that \(\displaystyle G_{2^m} \leqslant A_{2^m}\), using the "usual mathematical induction strategy".

The second part (which does not require induction at all) shows that if the result holds for $n=2^m$ then it also holds for any smaller (positive) value of $n$. Since every natural number is less than some power of $2$, it follows that the result holds for all $n$.

 

[Evgeny.Makarov]

This is standard mathematical induction. If you need to prove some statement $\forall n\,P(n)$ by induction, it does not mean that you necessarily have to prove $P(0)$ and $\forall n\,(P(n)\to P(n+1))$. More precisely, when one says that they is going to prove some claim by induction, the first thing they have to provide is what I call the induction statement, i.e., some predicate $Q(m)$. This may or may not coincide with the original predicate $P(n)$. Once $Q(m)$ is fixed, the proof by induction proceeds by proving $Q(0)$ and $\forall m\,(Q(m)\to Q(m+1))$. Thus one gets $\forall m\,Q(m)$. Then they have to prove $(\forall m\,Q(m))\to(\forall n\,P(n))$.

Guessing the predicate $Q(m)$ from the original $P(n)$ is sometimes nontrivial. For example, to prove the property $P(n)\equiv f_{2n+1}=f_{n}^2+f_{n+1}^2$ of Fibonacci numbers one has to generalize it to $Q(m)\equiv f_{m+n+1}=f_mf_n+f_{m+1}f_{n+1}$; otherwise the induction step does not go through. Then once we have $\forall m\,Q(m)$ for each $n$, we set $m=n$.

So instead of proving $\forall n\,P(n)$ in a standard way, one may choose another parameter, such as $\lfloor n/2\rfloor$ or the number of prime divisors of $n$, and perform induction on this parameter. In the latter case this means choosing $Q(m)$ to be the following statement: $P(n)$ holds for all $n$ that are factored into $m$ prime divisors.

In the AM-GM inequality $Q(m)$ is $G_{2^m}\le A_{2^m}$, and once this is proved for all natural $m$, we deduce from it (without induction) that $G_n\le A_n$ for all $n$.

 

[Math Amateur]

The proof consists of two separate parts. The first part proves by induction on $m$ that \(\displaystyle G_{2^m} \leqslant A_{2^m}\), using the "usual mathematical induction strategy".

The second part (which does not require induction at all) shows that if the result holds for $n=2^m$ then it also holds for any smaller (positive) value of $n$. Since every natural number is less than some power of $2$, it follows that the result holds for all $n$.

Thanks Opalg ... that clarifies the matter a great deal ...

Appreciate your help ...

Peter

- - - Updated - - -

This is standard mathematical induction. If you need to prove some statement $\forall n\,P(n)$ by induction, it does not mean that you necessarily have to prove $P(0)$ and $\forall n\,(P(n)\to P(n+1))$. More precisely, when one says that they is going to prove some claim by induction, the first thing they have to provide is what I call the induction statement, i.e., some predicate $Q(m)$. This may or may not coincide with the original predicate $P(n)$. Once $Q(m)$ is fixed, the proof by induction proceeds by proving $Q(0)$ and $\forall m\,(Q(m)\to Q(m+1))$. Thus one gets $\forall m\,Q(m)$. Then they have to prove $(\forall m\,Q(m))\to(\forall n\,P(n))$.

Guessing the predicate $Q(m)$ from the original $P(n)$ is sometimes nontrivial. For example, to prove the property $P(n)\equiv f_{2n+1}=f_{n}^2+f_{n+1}^2$ of Fibonacci numbers one has to generalize it to $Q(m)\equiv f_{m+n+1}=f_mf_n+f_{m+1}f_{n+1}$; otherwise the induction step does not go through. Then once we have $\forall m\,Q(m)$ for each $n$, we set $m=n$.

So instead of proving $\forall n\,P(n)$ in a standard way, one may choose another parameter, such as $\lfloor n/2\rfloor$ or the number of prime divisors of $n$, and perform induction on this parameter. In the latter case this means choosing $Q(m)$ to be the following statement: $P(n)$ holds for all $n$ that are factored into $m$ prime divisors.

In the AM-GM inequality $Q(m)$ is $G_{2^m}\le A_{2^m}$, and once this is proved for all natural $m$, we deduce from it (without induction) that $G_n\le A_n$ for all $n$.

Hi Evgeny ...

... thanks for a really informative post ...

... still reflecting on what you have said ...

Appreciate your help ...

Peter