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).
A simplified case
If there are two elements in the series, the AM-GM states this:
The proof for this simplified case is quite simple:
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 , or when the number of elements in the set is 2.
The method of inductive proof is proving a base case, , and proving that if this base case is true then the case where is also true. This would mean that the statement is true for all instances of .
Here the base case is , which we have just proved to be true. We can now prove that this is true when , or when there are 4 elements in the set: .
The arithmetic mean, or AM of the set is
We can split this set into two halves. One contains , and the other contains .
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,
Notice that both of the two halves are of length 2, or in the general case, . Having already proved the previous case, we can say,
This itself is another arithmetic mean. Applying the base case again:
So we have
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.
If the arithmetic mean of a set, is a, then
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
as we proved before. According to the lemma, we can substitute:
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 . Then prove by induction, again, that it is true for .
This method of proof is called forward-backward induction. This proof was discovered by Augustin-Louis Cauchy.