Several Proofs of the AM–GM Inequality

In one sentence

The AM–GM inequality: if $a_{1}, \dots, a_{n}$ are positive reals, then

A = \frac{a _{1} + a _{2} + \dots + a _{n}}{n} \geq n a_{1} a_{2} \dots a_{n} = G .

Inducting on $n$ , the step “from $n$ to $n + 1$ ” is awkward: the extra number does not combine well with the others. But “from $n$ to $2 n$ ” is smooth: split the $2 n$ numbers into two halves, use the induction hypothesis on each half, then use $n = 2$ once on the two means. So take a different route:

jump up: $n = 2$ holds and $n \Rightarrow 2 n$ , so it holds for $2, 4, 8, 16, \dots$ ;
walk back: derive the case $n$ from the case $n + 1$ , filling in the gaps one rung at a time.

This is backward induction: if ① the statement holds for infinitely many $n$ and ② $P (n + 1)$ implies $P (n)$ , then the statement holds for every $n$ .

AM–GM: double first, then go back

Step 1 / 6

n = 2
The case of two numbers is a square: $(a - b)^{2} \geq 0$ , which expands to $\frac{a + b}{2} \geq ab$ , with equality if and only if $a = b$ .

$a + b - 2 ab = (a - b)^{2} \geq 0$
Doubling: n ⇒ 2n
Which rungs are lit
Filling down: n+1 ⇒ n
All the way in one step
Why this is enough

Predict first

To get the case of $11$ numbers directly from the case of $16$ , how many numbers must you add after $a_{1}, \dots, a_{11}$ , and which numbers?

5

copies of

1

5

copies of

A

(the mean of the

11

numbers)

5

copies of

G

(the geometric mean of the

11

numbers)

16

copies of

A

Choose an answer first; then you can see the result.

Stop 1 · Inequalities: one result, two inductions

One problem, several solutions

Prove that the arithmetic mean $A$ of $n$ positive numbers $a_{1}, \dots, a_{n}$ is at least their geometric mean $G$ .

Straight n ⇒ n+1: adjust, then induct

Assume it for $n$ numbers and take $n + 1$ numbers with mean $A$ . We may assume $a_{n} \leq A \leq a_{n + 1}$ (the smallest is at most the mean, the largest at least the mean).

Replace $a_{n}, a_{n + 1}$ by $A$ and $a_{n} + a_{n + 1} - A$ : the sum stays the same, and the product

$A (a_{n} + a_{n + 1} - A) - a_{n} a_{n + 1} = (A - a_{n}) (a_{n + 1} - A) \geq 0$

does not decrease. The other $n$ numbers $a_{1}, \dots, a_{n - 1}, a_{n} + a_{n + 1} - A$ have sum $(n + 1) A - A = n A$ , so their mean is also $A$ . By the induction hypothesis their product is $\leq A^{n}$ , so

$a_{1} \dots a_{n + 1} \leq a_{1} \dots a_{n - 1} \cdot (a_{n} + a_{n + 1} - A) \cdot A \leq A^{n} \cdot A = A^{n + 1} .$

CostDone in one go, but you must think of “replacing the largest and the smallest”.

Doubling + going back (backward induction)

$n = 2$ : a square. $n \Rightarrow 2 n$ : the induction hypothesis once on each half, then $n = 2$ once on the two means. $n + 1 \Rightarrow n$ : add one copy of the mean $A$ .

n = 6

: add two copies of

A

to make

8

. Change some of the numbers and watch the geometric mean stay at most

A

. When are they equal?

CostEvery step is mechanical, no inspiration needed; the price is an extra round trip.

Both proofs have to “arrange” something: one arranges an adjustment that keeps the mean, the other arranges $2^{k}$ numbers. What they share: the mean $A$ never moves.

Stop 2 · Functions: midpoint convexity gives n-point convexity

The same “doubling + going back” carries over to functions unchanged.

Example A function $f$ satisfies $f (\frac{x + y}{2}) \leq \frac{f ( x ) + f ( y )}{2}$ for all real $x, y$ . Prove that for every $n$ and all $x_{1}, \dots, x_{n}$ ,

f (\frac{x _{1} + \dots + x _{n}}{n}) \leq \frac{f ( x _{1} ) + \dots + f ( x _{n} )}{n} .

Jensen's inequality by backward induction

Step 1 / 4

n = 2
This is exactly the given condition.

$f (\frac{x + y}{2}) \leq \frac{f ( x ) + f ( y )}{2}$
n ⇒ 2n
n+1 ⇒ n
Tidy up

Stop 3 · When you cannot get back down

Condition ② of backward induction is the real hurdle: you must be able to get the smaller case out of the larger one. AM–GM can go back because you can add a number that “does nothing”. If you cannot go back, a statement proved for infinitely many $n$ really may hold only for those $n$ .

Break it

Counterexample lab: remove one condition

Conclusion: The statement holds for every $n$

AM–GM: every $P (2^{k})$ is proved, and adding one $A$ takes you from $n + 1$ down to $n$ . Press ③ and the whole ladder lights up.

Practice

Exercise 1Basic

Positive numbers $a, b, c$ satisfy $a + b + c = 6$ . Find the maximum of $ab c$ .

Exercise 2Basic

You prove AM–GM for $19$ numbers by “doubling + all the way in one step”. What is the fewest numbers you must add?

Exercise 3Advanced

Find the minimum of $x + \frac{4}{x ^{2}}$ for $x > 0$ .

Exercise 4Challenge

Let $x_{1}, \dots, x_{n}$ be positive and $G = n x_{1} \dots x_{n}$ . Prove by backward induction that $(1 + x_{1}) (1 + x_{2}) \dots (1 + x_{n}) \geq (1 + G)^{n}$ .

In one sentence

AM–GM: double first, then go back

Stop 1 · Inequalities: one result, two inductions

Straight n ⇒ n+1: adjust, then induct

Doubling + going back (backward induction)

Stop 2 · Functions: midpoint convexity gives n-point convexity

Jensen's inequality by backward induction

Stop 3 · When you cannot get back down

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

Proving it for powers of 2 only, then claiming it for every n

Padding with the wrong number