Difference between revisions of "Proofs of AM-GM"
Etmetalakret (talk | contribs) m (Categories misspelling) |
Etmetalakret (talk | contribs) m |
||
Line 1: | Line 1: | ||
− | This pages lists some proofs of the weighted [[AM-GM]] | + | This pages lists some proofs of the weighted [[AM-GM Inequality]]. The inequality's statement is as follows: for all nonnegative reals <math>a_1, \dotsc, a_n</math> and nonnegative reals <math>\lambda_1, \dotsc, \lambda_n</math> such that <math>\sum_{i=1}^n \lambda_i = 1</math>, then |
<cmath> \sum_{i=1}^n \lambda_i a_i \ge \prod_{i=1}^n a_i^{\lambda_i}, </cmath> | <cmath> \sum_{i=1}^n \lambda_i a_i \ge \prod_{i=1}^n a_i^{\lambda_i}, </cmath> | ||
with equality if and only if <math>a_i = a_j</math> for all <math>i,j</math> such that <math>\lambda_i, \lambda_j \neq 0</math>. | with equality if and only if <math>a_i = a_j</math> for all <math>i,j</math> such that <math>\lambda_i, \lambda_j \neq 0</math>. |
Revision as of 23:40, 31 December 2021
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
[hide]Proofs of Unweighted AM-GM
These proofs use the assumption that , for all integers .
Proof by Cauchy Induction
We use Cauchy Induction, a variant of induction in which one proves a result for , all powers of , and then that implies .
Base Case: The smallest nontrivial case of AM-GM is in two variables. By the properties of perfect squares (or by the Trivial Inequality), with equality if and only if , or . Then because and are nonnegative, we can perform the following manipulations: with equality if and only if , just as before. This completes the proof of the base case.
Powers of Two: We use induction. Suppose that AM-GM is true for variables; we will then prove that the inequality is true for . Let be any list of nonnegative reals. Then, because the two lists and , have variables each, Adding these two inequalities together and dividing by two yields Then by AM-GM in two variables, Combining this inequality with the previous one yields unweighted AM-GM in variables, with one exception — equality.
For equality, note that every inequality mentioned must have equality as well; thus, inequality holds if and only if all the numbers in are the same, all the numbers in are the same, and . From here, it is trivial to show that this implies , which is the equality condition for unweighted AM-GM in variables.
This completes the induction and implies that unweighted AM-GM holds for all powers of two.
Backward Step: Assume that AM-GM holds for variables. We will then use a substitution to derive AM-GM for variables. Letting , we have that Because we assumed AM-GM in variables, equality holds if and only if . However, note that the last equality is implied if all the numbers of are the same; thus, equality holds if and only if .
We then simplify the lefthand side. Multiplying both sides of the fraction by and combining like terms, we get that Thus, Raising both sides to the th power yields From here, we divide by and take the root to get that Every step we took preserves our earlier equality condition, which proves that AM-GM holds for variables. This completes the backward step, which proves the unweighted AM-GM Inequality.
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 Calculus
We will start the proof by considering the function . We will now find the maximum of this function. We can do this simply using calculus. We need to find the critical points of , we can do that by finding and setting it equal to . Using the linearity of the derivative . We need Note that this is the only critical point of . We can confirm it is the maximum by finding it's second derivative and making sure it is negative. letting x = 1 we get . Since the second derivative , is a maximum. . Now that we have that is a maximum of , we can safely say that or in other words . We will now define a few more things and do some manipulations with them. Let , with this notice that . This fact will come into play later. now we can do the following, let and plug this into , we get Adding all these results together we get Now exponentiating both sides we get This proves the AM-GM inequality.
Proof of Weighted AM-GM
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.