A proof of the Arithmetic-Geometric mean inequality.

· Uncategorized

The following result is essential to the proof.

If xεR, x≥0, then (1+x/(n-1))n-1≤(1+x/n)n, nεω, n≥2. Equality holds iff x=0. (*)

Proof

If xεR, x≥0, and nεω, n≥2, then the following expression may be expanded using the binomial Theorem …

(1+x/n)n-(1+x/(n-1))n-1

= 1 +∑1≤r≤n n(n-1) … (n-r+1)/r! (x/n)r

-(1 +∑1≤r≤n-1 (n-1)(n-2) … (n-r)/r! (x/(n-1))r)

=∑1≤r≤n-1 xr/r![(n-1)/n … (n-r+1)/n – (n-2)/(n-1) … (n-r)/(n-1)]

+ (x/n)n.

It is straightforward to show that …

[(n-1)/n … (n-r+1)/n – (n-2)/(n-1) … (n-r)/(n-1)]>0 since, (n-1)/n > (n-2)/(n-1) … and (n-r+1)/n > (n-r)/(n-1).

Hence it follows that (1+x/n)n-(1+x/(n-1))n-1≥(x/n)n if x≥0.

The result, i.e. (1+x/(n-1))n-1≤(1+x/n)n, follows easily from this, and if equality holds, then (x/n)n = 0, and so x=0.

Statement and proof of the Arithmetic-Geometric Mean inequality.

For each nεω, let P(n) be the proposition that for any set of non-negative numbers a1, a2, … an,

(a1 + a2 + …. + an)/n ≥(a1a2 … an)1/n

with equality if and only if a1 = a2 = a3 … = an.

Proof

P(1) is trivially true, i.e. a1/1 = a11/1.

P(2) If a1 and a2 are ≥0 then it is easily shown that …

(a1 + a2)2≥ 4a1a2 and so (a1 + a2)/2 ≥ √(a1a2).

If (a1+ a2)/2 = √(a1a2) then (a1 – a2)2 = 0 and so a1 = a2.

Now suppose that P(n-1) is true for n-1 ε ω and n – 1≥ 2.

Suppose that a1, a2, … an are n non-negative numbers. We can assume that a1≤a2≤a3 …≤ an. If not then we can choose a re-arrangement of a1, a2, … an that does have this property. It now follows that …

(a2 + a3 + … an)/(n-1)≥(a2a3 … an)1/(n-1)or

a2a3… an≤((a2+ a3+ … an)/(n-1))(n-1) with equality iff a2 = a3 = a4 … = an.

Now let D = (a2 – a1) + (a3 – a1) + … + (an – a1). Clearly D≥0 with equality iff a1=a2=a3 … = an.

D = a2 + a3 + … +an – (n-1)a1 and so, a1 + D/(n-1) = (a2 + a3 + … + an)/(n-1).

So, a2a3… an≤(a1 + D/(n-1))(n-1) with equality iff a2= a3= a4… = an.

Hence, multiplying by a1 we get a1a2a3… an≤a1(a1+ D/(n-1))(n-1).

Applying (*) above we get a1a2a3… an≤a1(a1+ D/(n-1))(n-1)≤(a1+ D/n)n, or

a1a2a3… an≤(a1+ D/n)n=((a1 + a2 + … an)/n)n, with equality iff D=0 or iff a1=a2=a3… = an.

Hence it follows that (a1 + a2 + … +an)/n≥ n√(a1a2 … an) with equality iff a1=a2=a3… = an. Thus P(n) is true and the result follows by the principle of Mathematical Induction.

Applications of the AGM to the sequence n1/n, where nεω, n≥1.

Numerical computation of the first few terms of this sequence shows that the first term 11/1 = 1, the second is 21/2 = √2 and the third term is 3√3 ( the maximum value of the sequence). For n≥3 the sequence appears to be monotone decreasing, tending to a limit of 1.

Firstly, 2 subsequent values cannot be equal. Otherwise n1/n = (n+1)1/(n+1) for some n. From this equation (if true) it follows that n(n+1) = (n+1)n. If n=1 then it follows that 1 = 2 which is obviously false. If n>1 then n and n+1 must have a common prime factor, again false since n and n+1 are coprime.

So, for all nεω, n≥1, either n1/n> (n+1)1/(n+1) or n1/n< (n+1)1/(n+1).

Suppose that n1/n> (n+1)1/(n+1). Then, n(n+1)> (n+1)n.

So, n(n+1)– nn> (n+1)n-nn and from this it follows that …

nn(n-1)> (n+1)n-1 + (n+1)n-2n + … + nn-1 >n(n(n+1))(n-1)/2 (applying the AGM).

Simplifying nn(n-1)>n(n(n+1))(n-1)/2gives n-1>((n+1)/n)(n-1)/2>1. Hence it follows that n≥3.

So, for all nεω, n≥3, n1/n> (n+1)1/(n+1).

To prove that lim n→∞ n1/n = 1, first observe that n1/n> 1 for all n> 1, otherwise n1/n≤1 for some n>1. n1/n≤ 1 implies that n≤1, which clearly gives a contradiction, so n1/n> 1 for all n> 1.

Next, if n>2, we apply the AGM inequality to the set of n positive numbers 1, 1, … ,1 (n-2 times),√n,√n.

This gives (n-2+2√n)/n>n1/n, or 1-2/n+2/√n>n1/n. This last inequality implies that as n→∞, n1/n approaches arbitrarily close to 1. Hence the result limn→∞ n1/n= 1.

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: