The AM-GM inequality

One of the most basic inequalities, the AM-GM inequality states that the AM (Arithmetic mean) of a series of real numbers is always greater or equal to the GM (Geometric mean).

Mathematically:

$\frac{x_1 + x_2 + \cdots + x_n}{n} \geq \sqrt[n]{x_1 x_2 \cdots x_n}$

A simplified case

If there are two elements in the series, the AM-GM states this:

$\frac{x+y}{2} \geq \sqrt{xy}$

The proof for this simplified case is quite simple:

$\begin{array}{l} \frac{x+y}{2} - \sqrt{xy} \\ = \frac{x - 2\sqrt{xy} + y}{2} \\ = \frac{(\sqrt{x} - \sqrt{y})^2}{2} \geq 0 \end{array}$

Now, however, it is not so obvious how to extend this proof to a set of three elements, or more. But there is a way, by induction, to prove this inequality for cases where the number of elements is a power of two.

The 2^k subcase

The base case states that the AM-GM inequality is true for $n=2$ , or when the number of elements in the set is 2.

The method of inductive proof is proving a base case, $2^k$ , and proving that if this base case is true then the case where $2^{k+1}$ is also true. This would mean that the statement is true for all instances of $2^k$ .

Here the base case is $n = 2^1$ , which we have just proved to be true. We can now prove that this is true when $n = 2^2$ , or when there are 4 elements in the set: $x_1, x_2, x_3, x_4$ .

The arithmetic mean, or AM of the set is

$\frac{x_1 + x_2 + x_3 + x_4}{4}$ .

We can split this set into two halves. One contains $x_1, x_2$ , and the other contains $x_3, x_4$ .

The point is that the arithmetic mean of the arithmetic means of the two halves is equal to the arithmetic mean of the whole. Or,

$\textrm{AM} = \frac{\frac{x_1+x_2}{2}+\frac{x_3+x_4}{2}}{2}$

Notice that both of the two halves are of length 2, or in the general case, $2^{k-1}$ . Having already proved the previous case, we can say,

$\textrm{AM} \geq \frac{\sqrt{x_1 x_2} + \sqrt{x_3 x_4}}{2}$

This itself is another arithmetic mean. Applying the base case again:

$\begin{array}{rcl} \textrm{AM} &\geq& \sqrt{\sqrt{x_1 x_2} \sqrt{x_3 x_4}} \\ &=& \sqrt[4]{x_1 x_2 x_3 x_4} \end{array}$

So we have

$\frac{x_1 + x_2 + x_3 + x_4}{4} \geq \sqrt[4]{x_1 x_2 x_3 x_4}$

which was what we wanted to prove.

The process for proving this for a higher power of 2, such as 8, 16, etc, is very similar to what we have just done.

The n-1 subcase

If the number of elements in the set is not a nice and even power of two, the above proof does not work. Instead, we use induction again, but this time from top-down.

We try to prove that if the inequality is true for a set with n elements, then it is also true for a set with n-1 elements.

Let’s first prove a lemma.

Lemma

If the arithmetic mean of a set, $x_1, x_2, \cdots, x_n$ is a, then

$\frac{x_1 + \cdots x_n + a}{n+1} = \frac{x_1 + \cdots + x_n}{n}$ .

Proof

$\begin{array}{l} \frac{x_1 + \cdots + x_n + a}{n+1} \\ =\frac{x_1 + \cdots + x_n + \frac{x_1 + \cdots + x_n}{n}}{n+1} \\ = \frac{\frac{(n+1)x_1 + \cdots + (n+1)x_n}{n}}{n+1} \\ = \frac{x_1 + \cdots + x_n}{n} \end{array}$

This lemma simply states that if you have the mean of a set, adding the mean to the set itself and finding the mean again would result in the same mean.

Now let’s prove the inequality when n=3.

Let a be the arithmetic mean of the set. Then

$\frac{x_1 + x_2 + x_3 + a}{4} \geq \sqrt[4]{x_1 x_2 x_3 a}$

as we proved before. According to the lemma, we can substitute:

$\begin{array}{rcl} \frac{x_1 + x_2 + x_3}{3} &\geq& \sqrt[4]{x_1 x_2 x_3 a} \\ a &\geq& \sqrt[4]{x_1 x_2 x_3 a} \\ a^4 &\geq& x_1 x_2 x_3 a \\ a^3 &\geq& x_1 x_2 x_3 \\ a &\geq& \sqrt[3]{x_1 x_2 x_3} \end{array}$

This completes our proof.

Of course I’ve proved it only for n=3, but the same method can be used to prove for any number where it is true for n+1.

To prove this for any integer n, first prove by induction that this is true for some number $2^k$ . Then prove by induction, again, that it is true for $2^k-1, 2^k-2, \cdots, n$ .

This method of proof is called forward-backward induction. This proof was discovered by Augustin-Louis Cauchy.

This entry was posted on Saturday, April 24th, 2010 at 5:01 pm and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

5 Responses to The AM-GM inequality

Cody W says:

April 25, 2010 at 8:25 pm

Wow… They taught us the AM-GM inequality at WCHS’ math club, so this is actually one of the VERY few times that I already knew a concept on your blog prior to reading it.

Reply
- luckytoilet says:
  
  April 25, 2010 at 8:32 pm
  
  Aha- But did you know how to prove it though?
  
  Is that math club at Western? Because I don’t think there’s a math club at my school (although I just started a computer science club).
  
  Reply
  - Cody W says:
    
    April 25, 2010 at 8:59 pm
    
    We weren’t supposed to, but we did anyways. There are two math clubs at Western, one for grade 10′s, another for grade 11′s and 12′s. How’s your club going?
    
    Reply
Anonymous says:

July 13, 2011 at 10:54 pm

The simplified case is incorrect (the one under ‘a simplified case’).
When making a common denominator, there should be another root (xy) on the top. Therefore it should read: [x - 2root(xy) + y] / 2.
: )

Dinzy

Reply
Bridget says:

May 11, 2013 at 8:09 pm

What’s Taking place i am new to this, I stumbled upon this I’ve found It positively useful and it has helped me out
loads. I am hoping to give a contribution & help different customers like its
aided me. Good job.

Reply

Lucky's Notes