Cauchy’s proof of the Arithmetic/Geometric mean inequality

The Arithmetic/Geometry mean inequality, often called the AM-GM inequality , states that:

\sqrt[n]{x_1 x_2 \ldots x_n} \le \left(\frac{x_1+x_2+\ldots+x_n}{n}\right)

There are quite a few proof of this, but there is a really interesting one due to Cauchy. It uses induction, but induction that goes backwards as well as forwards.

Define P(n) to mean that the AM-GM inequality holds for arbitrary x_1, x_2, \ldots , x_n. In this notation, the stages of the proof are:

  • Show P(2) holds
  • Show that if P(n) holds, then P(2n) holds.
  • Show that if P(n) holds, then P(n-1) holds.

Of course, this will show that P(n) holds for all n. It is an interesting way of going about it though. And the great thing is, proving each of these sub-cases is quite easy!

P(2) is simple, as the true inequality 0 \le (x-y)^2 can be expanded, 4xy added to each side and factorised to give xy \le \frac{1}{4}(x+y)^2, which is what we want.

Suppose that P(n) is true. Then P(2n) easily follows by just splitting it into two products of n numbers:

Between the first and second line P(n) has been applied, and between the third and forth lines P(2) is applied.

Finally, we must show that if P(n) holds, then P(n-1) also holds. The obvious way to go about this is to take the n-1 numbers and add a new number to the end of it to make n numbers, and hope we can choose a number which doesn’t change anything. It’s not too obvious what this number should be, but let’s call it A:

Ax_1x_2\ldots x_{n-1} \le \left(\frac{A+x_1+\ldots+x_{n-1}}{n}\right)^n

We want to somehow be able to factor the A back out so that we have:

\left(\frac{A+x_1+\ldots+x_{n-1}}{n}\right)^n = A \left(\frac{x_1+\ldots+x_{n-1}}{n-1}\right)^{n-1}

A value of A which does this nicely is:

A = \left(\frac{x_1+\ldots+x_{n-1}}{n-1}\right)

As then we have:

Hence P(n-1) and so we are done.

Advertisements

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

%d bloggers like this: