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.

4 thoughts on “The AM-GM inequality

  1. 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.

    1. 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).

      1. 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?

  2. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s