Difference between revisions of "Proofs of AM-GM"
m (→Proof by Convexity) |
(Made a MAJOR clarification on the 'alternate proof by convexity' (weighted inequality)) |
||
Line 31: | Line 31: | ||
<cmath> (r_i +1)^{\lambda_i} \le \exp(\lambda_i r_i) .</cmath> | <cmath> (r_i +1)^{\lambda_i} \le \exp(\lambda_i r_i) .</cmath> | ||
Multiplying <math>n</math> such inequalities gives us | Multiplying <math>n</math> such inequalities gives us | ||
− | <cmath> | + | |
− | + | <cmath>\prod_{i=1}^n (r_i + 1)^{\lambda_{i}} \le \prod_{i=1}^n \exp \lambda_i r_i </cmath> | |
− | <cmath> \prod_{i=1}^n a_i^{\lambda_i} \ | + | |
− | + | Evaluating the left hand side: | |
+ | |||
+ | <cmath>\prod_{i=1}^n (r_i + 1)^{\lambda_{i}} = \frac{\prod_{i=1}^n a_i^{\lambda_i} }{ (\sum_{j=1}^n \lambda_j a_j)^{\sum_{j=1}^n \lambda_i} } = \frac{\prod_{i=1}^n a_i^{\lambda_i} }{ \sum_{j=1}^n \lambda_j a_j } ,</cmath> | ||
+ | |||
+ | for | ||
+ | |||
+ | <cmath> \sum_{j=1}^n \lambda_i = 1 .</cmath> | ||
+ | |||
+ | Evaluating the right hand side: | ||
+ | |||
+ | <cmath> \prod_{i=1}^n \exp \lambda_i r_i = \prod_{i=1}^n \exp (\frac{a_i \lambda_i}{ \sum_{i=1}^n \lambda_j a_j} - \lambda_i) = \exp (\frac{\sum_{i=1}^n a_i \lambda_i}{ \sum_{i=1}^n \lambda_j a_j} - \sum_{i=1}^n \lambda_i) = \exp 0 = 1 .</cmath> | ||
+ | |||
+ | Substituting the results for the left and right sides: | ||
+ | |||
+ | <cmath> \frac{\prod_{i=1}^n a_i^{\lambda_i} }{ \sum_{j=1}^n \lambda_j a_j } \le 1 </cmath> | ||
+ | |||
+ | <cmath> \prod_{i=1}^n a_i^{\lambda_i} \le \sum_{j=1}^n \lambda_j a_j = \sum_{i=1}^n \lambda_i a_i , </cmath> | ||
+ | |||
+ | as desired. <math>\blacksquare</math> | ||
== Proofs of Unweighted AM-GM == | == Proofs of Unweighted AM-GM == |
Revision as of 22:57, 20 May 2013
This pages lists some proofs of the weighted AM-GM Inequality. The inequality's statement is as follows: for all nonnegative reals and nonnegative reals
such that
, then
with equality if and only if
for all
such that
.
We first note that we may disregard any for which
, as they contribute to neither side of the desired inequality. We also note that if
and
, for some
, then the right-hand side of the inequality is zero and the left hand of the inequality is greater or equal to zero, with equality if and only if
whenever
. Thus we may henceforth assume that all
and
are strictly positive.
Contents
Complete Proofs
Proof by Convexity
We note that the function is strictly concave. Then by Jensen's Inequality,
with equality if and only if all the
are equal.
Since
is a strictly increasing function, it then follows that
with equality if and only if all the
are equal, as desired.
Alternate Proof by Convexity
This proof is due to G. Pólya.
Note that the function is strictly convex. Let
be the line tangent to
at
; then
. Since
is also a continuous, differentiable function, it follows that
for all
, with equality exactly when
, i.e.,
with equality exactly when
.
Now, set
for all integers
. Our earlier bound tells us that
so
Multiplying
such inequalities gives us
Evaluating the left hand side:
for
Evaluating the right hand side:
Substituting the results for the left and right sides:
as desired.
Proofs of Unweighted AM-GM
These proofs use the assumption that , for all integers
.
Proof by Rearrangement
Define the sequence
as
, for all integers
. Evidently these sequences are similarly sorted. Then by the Rearrangement Inequality,
where we take our indices modulo
, with equality exactly when all the
, and therefore all the
, are equal. Dividing both sides by
gives the desired inequality.
Proof by Cauchy Induction
We first prove that the inequality holds for two variables. Note that are similarly sorted sequences. Then by the Rearrangement Inequality,
with equality exactly when
.
We next prove that if the inequality holds for variables (with equality when all are equal to zero), than it holds for
variables (with equality when all are equal to zero). Indeed, suppose the inequality holds for
variables. Let
denote the arithmetic means of
,
,
, respectively; let
denote their respective geometric means. Then
with equality when all the numbers
are equal, as desired.
These two results show by induction that the theorem holds for , for all integers
. In particular, for every integer
, there is an integer
such that the theorem holds for
variables.
Finally, we show that if and the theorem holds for
variables, then it holds for
variables
with arithmetic mean
and geometric mean
. Indeed, set
for
, and let
for
. Then
It follows that
, or
, with equality exactly when all the
are equal to
.
The last two results show that for all positive integers , the theorem holds for
variables. Therefore the theorem is true.