Using strong induction to get the AM-GM inequality for $2^n$ numbers

Question

The arithmetic mean of $k$ numbers $a_1, a_2, \ldots, a_k$ is their average $\frac{a_1+a_2+\cdots+a_k}{k}=AM$. Their geometric mean is $\sqrt[k]{a_1a_2\cdots a_k}=GM$. I am asked to show this:

Use induction to prove: If $k=2^n$ and if all the numbers $a_1, a_2, \ldots, a_k$ are nonnegative, then $AM \geq GM$.

I'll be honest, I have no work for this problem. I've looked into many examples of strong induction, but most of them are abstract. Please give me insight for what method to best utilize for strong induction.

Answer 1

The case $k=2^n$ can be proved using ordinary induction on $n$. The induction argument is structurally natural, and there is no reason to think that there is a smoother proof by strong induction.

The standard proof, due to Cauchy, can be found here. Full details are given, so the link should be sufficient. If you have trouble with the induction step, work out what the proof says for the particular cases $k=4$, then $k=8$, and everything will be clear.

Cauchy actually proved the full Arithmetic Mean/Geometric Mean Inequality, by first dealing with the cases $k=2^n$, and then going backwards to deal with $k$ not a power of $2$. It is an elementary but very clever proof.

Answer 2

The use of induction (first ordinary induction to prove the result for powers of $2$, then upward-downward induction for the general case) to prove the Arithmetic-Geometric Mean Inequality appears in my lecture notes on induction (Theorem 21 in $\S 12$).

I agree that this argument is somewhat tricky. I am currently teaching a "Spivak calculus course" (i.e., very strong, very committed university freshmen) and I put this argument into my notes (which originated in a different undergraduate course) expressly for the current course but have not, so far, had a chance to mention it in class. I think many if not most young students would have trouble supplying a complete proof.