A General Proof of the Arithmetic-Geometric Mean Inequality

几何-算术均值不等式的一般证明 苏剑林 · 2009-08-24 · Mathematics proof inequality

This proof was worked out by the site owner after a long period of independent research. Anyone reposting it must credit the original author and source, otherwise copyright will be pursued! (There are a lot of formulas here — using Firefox is recommended.)

This inequality has a long history. Starting from $\frac{a+b}{2} \geq \sqrt{ab}$, people gradually discovered that as long as $a_1,a_2,...,a_n \geq 0$, it must be true that $\frac{a_1+a_2+...+a_n}{n} \geq \sqrt[n]{a_1 a_2...a_n}$. For small values of n, this has long been provable, but a proof for the general case is a more recent development.

I first encountered this inequality quite early on (I think it was three years ago, when I was in sixth grade), and ever since then I kept searching for a proof of it. But apart from the case n=2, I never succeeded — until three months ago, during a math class, while zoning out, I suddenly figured it out (^_^). At first I proved the case n=3, and then things fell into place one after another, and I was able to prove that the inequality holds for any n. more

In fact, the inequality above is equivalent to $a_1^n+a_2^n+...+a_n^n \geq n a_1 a_2...a_n$, and the goal of this post is to prove this latter inequality. The method used is mathematical induction: the condition for the inequality to hold at n=k is that it already holds at n=k-1, n=k-2, ..., n=1, and since we can directly prove the case n=2, we can build the proof up step by step. The proof is presented below (here the letters a, b, c, etc. all denote non-negative numbers):

Before giving the general proof, let's look at a couple of examples.

(1) Prove: $a^2+b^2 \geq 2ab$

Let's set aside the textbook proof and instead let $a\leq b,b=a+x$, so that we have $a^2+(a+x)^2 \geq 2a(a+x)$. Expanding this gives $2a^2+2ax+x^2 \geq 2a^2+2ax$, which is clearly true.

(2) Prove: $a^3+b^3+c^3 \geq 3abc$

Using the same approach, let $a\leq b\leq c,b=a+x,c=a+y$, so that we have $a^3+(a+x)^3+(a+y)^3 \geq 3a(a+x)(a+y)$. Expanding $a^3+a^3+3a^2 x+3ax^2+x^3+a^3+3a^2 y+3ay^2+y^3 \geq 3a^3+3a^2 x+3a^2 y+3axy$

gives: $x^3+y^3+3a(x^2+y^2) \geq 3axy$, and clearly $x^2+y^2 \geq xy$, so the statement holds.

Now that you've seen these, do you get the trick behind the proof? The proof for the general case is as follows.

Elementary-mathematics version

Suppose that for the values 1, 2, ..., n-1 the inequality already holds; we now prove: $a_1^n+a_2^n+...+a_n^n \geq n a_1 a_2...a_n$

Let $a_{i+1} \geq a_i,a_1=a,a_{i+1}=a+x_i$, where i = 1, 2, 3, ..., n. This becomes:

$a^n+(a+x_1)^n+...+(a+x_{i-1})^n \geq na(a+x_1)...(a+x_{i-1})$, and expanding via Pascal's Triangle:

$$\begin{aligned}a^n+ \\ a^n+C_n^1 a^{n-1}x_1+C_n^2 a^{n-2}x_1^2+...+x_1^n+ \\ a^n+C_n^1 a^{n-1}x_2+C_n^2 a^{n-2}x_2^2+...+x_2^n+ \\ ......+ \\ a^n+C_n^1 a^{n-1}x_{n-1}+C_n^2 a^{n-2}x_{n-1}^2+...+x_{n-1}^n \geq \\ na^n+na^{n-1}(x_1+x_2+...+x_{n-1})+na^{n-2}(x_1 x_2+x_1 x_3+...+x_{n-2}x_{n-1})+ \\ ...+nax_1 x_2...x_{n-1}\end{aligned}$$

Note: here $C_a^b$ denotes the binomial coefficient, which is also the formula for computing entries in Pascal's Triangle. It is defined as: the number of distinct ways to choose b items out of a distinct items, computed by the rule: $C_a^b=\frac{a!}{b!(a-b)!}$

Cancelling matching terms and combining, we get

$$\begin{aligned}{C_n^2}/{n}a^{n-2}(x_1^2+...x_{n-1}^2)+{C_n^3}/{n}a^{n-3}(x_1^3+...x_{n-1}^3)+...+{x_1^n+x_2^n+...+x_{n-1}^n}/{n} \\ \geq a^{n-2}(x_1 x_2+...+x_{n-2}x_{n-1})+a^{n-3}(x_1 x_2 x_3+...+x_{n-3}x_{n-2}x_{n-1})+...\end{aligned}$$

$+ax_1 x_2...x_{n-1}$ ————(A)

To prove the original statement, we must show that the equation above holds.

The number of terms in $(x_1 x_2+...+x_{n-2}x_{n-1})$ is $C_{n-1}^2$, and the number of terms in $(x_1 x_2 x_3+...+x_{n-3}x_{n-2}x_{n-1})$ is $C_{n-1}^3$.

**By multiplying through cyclic permutations, one can see that when

$$a_1^p+a_2^p+...+a_p^p \geq p a_1 a_2...a_p$$

holds, it must follow that ${C_{n-1}^p}/{n-1}(x_1^p+...+x_{n-1}^p) \geq (x_1 x_2...x_p+...+x_{n-p}x_{n-p+1}...x_{n-1})$**

And since we also have ${C_{n}^p}/{n} \geq {C_{n-1}^p}/{n-1}$, it follows that in (A), every term on the left is no smaller than the corresponding term on the right, so (A) holds. Therefore $a_1^n+a_2^n+...+a_n^n \geq n a_1 a_2...a_n$ holds.

After reading through this, does it feel quite complicated? Trust me — if you read it carefully, you'll find it's actually quite simple. Especially for proving special cases with small n, this is absolutely the most elegant method!