Proving the AM-GM Inequality by induction

Question

I am required to prove the AM-GM inequality using induction but via this route:

(i) Let $a_1$, $a_2$, ..., an be a sequence of positive numbers. Denote their sum by $s$ and their geometric mean by $G$. Let $a$ and $b$ be two terms in the sequence such that $a>G>b$. Show that replacing $a$ by $G$ and $b$ by $ab/G$ does not alter the geometric mean, and the sum does not increase.

(ii) Use (i) and mathematical induction to prove $s ≥ nG$.

Part (i) is simple, and I am able to prove part (ii) using repeated substitution (similar to a method described in Wikipedia), but I am required to prove (ii) using induction instead. How can this be done using part (i) and using induction? Thank you!

Answer 1

To prove A.M.-G.M. Inequality using induction, we use backward induction.

Backward induction is basically this :-
Suppose the statement is $P_n$.
We follow the given steps.

1. Find a sequence $\{n_k\}_{k=1}^{\infty}$ such that $\{P_{n_1}, P_{n_2}, ...\}$ are true.
2. Show that $P_{k+1}$ true $\implies P_k$ true.

To prove A.M.-G.M. Inequality, we assume $P_n \implies \frac{x_1+x_2+...+x_n}n \ge \sqrt[n]{x_1x_2....x_n}$

Now to do the first step, we prove $P_{n}$ true $\implies P_{2n}$ true.

We do so like this :

Given, $\frac{x_1+x_2+....+x_n}n \ge \sqrt[n]{x_1x_2....x_n}$.
Also $\frac{x_{n+1}+x_{n+2}+....+x_{2n}}n \ge \sqrt[n]{x_{n+1}x_{n+2}....x_{2n}}$

Now, $\frac{x_1+x_2+....+x_n+x_{n+1}+x_{n+2}+....+x_{2n}}{2n} = \frac12 \{\frac{x_1+x_2+....+x_n}n + \frac{x_{n+1}+x_{n+2}+....+x_{2n}}n\}$
$\ge \frac12\{\sqrt[n]{x_1x_2....x_n} + \sqrt[n]{x_{n+1}x_{n+2}....x_{2n}}\}$
$\ge \sqrt{\sqrt[n]{x_1x_2....x_{2n}}}$
$= \sqrt[2n]{x_1x_2....x_{2n}}$

Now we know, $P_2$ true $\implies P_4$ true $\implies P_8$ true $\implies ....$
Therefore, $P_n$ is true when $n = 2^k$ for all $k$

The case for $P_2$ is very basic and I am leaving it to you guies. So this leaves us with the second part of the proof, that is if $P_{k+1}$ is true, then $P_k$ is true.

First of all, I want to say one thing, although everyone knows it, that A.M.-G.M. inequality is true for any set of Real Numbers. So our idea to prove the second part is to choose such a $x_{k+1}$ that simplifies our work to a great extent.

Let $x_{k+1} = \frac{x_1+x_2+...+x_k}k$

All we know is that $P_{k+1}$ is true.
$\implies \frac{x_1+x_2+....+x_{k+1}}{k+1} \ge \sqrt[k+1]{x_1x_2....x_{k+1}}$
$\implies \frac{x_1+x_2+....+x_k+\frac{x_1+x_2+...+x_k}k}{k+1} \ge \sqrt[k+1]{x_1x_2....x_k\frac{x_1+x_2+...+x_k}k}$ $\implies \frac{x_1+x_2+...+x_k}k \ge (x_1x_2....x_k)^{\frac1{k+1}}(\frac{x_1+x_2+...+x_k}k)^{\frac1{k+1}}$
$(\frac{x_1+x_2+...+x_k}k)^{\frac k{k+1}} \ge (x_1x_2....x_k)^{\frac1{k+1}}$
$\implies \frac{x_1+x_2+...+x_k}k \ge \sqrt[k]{x_1x_2....x_k}$
$\implies P_k$ is true

Hence we are done by backward induction.