Proof of the inequality of arithmetic and geometric means by induction

Proof

We argue by induction on the number of terms. All computations take place in the ordered field $\R$.

1. For nonnegative reals $x_1, \dots, x_n$, let $P = x_1 \cdots x_n$ and $\mu = (x_1 + \dots + x_n)/n$. Then $P \ge 0$ and $\mu \ge 0$.
2. The geometric mean $g = \sqrt[n]{P}$ is the real number $g \ge 0$ with $g^n = P$.
3. Lemma. If $0 \le a < b$ and $n \ge 1$, then $a^n < b^n$. For $n = 1$ this is the hypothesis. If $a^n < b^n$, then $a^{n+1} = a^n a \le a^n b < b^n b = b^{n+1}$, since $a^n \ge 0$ and $b > 0$.
4. Claim $C(n)$: for all nonnegative $x_1, \dots, x_n$, we have $P \le \mu^n$, and $P < \mu^n$ unless all $x_i$ are equal. We prove $C(n)$ for each $n \ge 1$ by induction.
5. Base case $n = 1$. Then $P = x_1 = \mu$, and the single number is equal to itself.
6. Induction step. Assume $C(n)$ for some $n \ge 1$. Let $x_1, \dots, x_{n+1} \ge 0$ have product $P$ and mean $\mu$.
7. If all $x_i$ are equal, then each equals $\mu$, and $P = \mu^{n+1}$.
8. Suppose not all $x_i$ are equal. Then some $x_k \ne \mu$. Say $x_k > \mu$. If all $x_i \ge \mu$, the sum exceeds $(n+1)\mu$, which is false. So some $x_j < \mu$. The case $x_k < \mu$ is the same with the inequalities reversed.
9. Reorder the numbers so that $x_n > \mu$ and $x_{n+1} < \mu$. This changes neither $P$ nor $\mu$. Also $\mu > x_{n+1} \ge 0$, so $\mu > 0$.
10. Let $y = x_n + x_{n+1} - \mu$. Then $y \ge x_n - \mu > 0$.
11. The $n$ numbers $x_1, \dots, x_{n-1}, y$ have sum $(n+1)\mu - \mu = n \mu$, so their mean is $\mu$.
12. Let $Q = x_1 \cdots x_{n-1}$, with $Q = 1$ when $n = 1$. Then $Q \ge 0$. By $C(n)$ for the numbers of step 11, $Q y \le \mu^n$.
13. Expand both sides to check that $\mu y - x_n x_{n+1} = (x_n - \mu)(\mu - x_{n+1})$. Both factors are positive by step 9, so $x_n x_{n+1} < \mu y$.
14. If $Q = 0$, then $P = 0 < \mu^{n+1}$, by step 9.
15. If $Q > 0$, then by steps 13 and 12, $P = Q x_n x_{n+1} < Q \mu y = \mu (Q y) \le \mu \cdot \mu^n = \mu^{n+1}$.
16. Steps 7, 14 and 15 prove $C(n+1)$. By induction, $C(n)$ holds for each $n \ge 1$.
17. Now let $g = \sqrt[n]{P}$. If $g > \mu$, the lemma gives $P = g^n > \mu^n$, against $C(n)$. So $g \le \mu$.
18. If all $x_i$ equal some $c$, then $P = c^n$ and $\mu = c$. Two distinct nonnegative numbers have distinct $n$th powers, by the lemma. Since $c \ge 0$ and $c^n = P = g^n$, we get $g = c$. So $g = \mu$.
19. If not all $x_i$ are equal, then $P < \mu^n$ by $C(n)$. If $g = \mu$, then $P = \mu^n$, which is false. So $g < \mu$.
20. Thus $\sqrt[n]{x_1 \cdots x_n} \le (x_1 + \dots + x_n)/n$, with equality if and only if $x_1 = \dots = x_n$.