Difference between revisions of "Proofs of AM-GM"
(started page; more proofs to come) |
(added a Pólya proof and the Cauchy induction proof) |
||
Line 9: | Line 9: | ||
=== Proof by Convexity === | === Proof by Convexity === | ||
− | We note that the [[function]] <math>x \mapsto \ln x</math> is | + | We note that the [[function]] <math>x \mapsto \ln x</math> is strictly [[concave]]. Then by [[Jensen's Inequality]], |
<cmath> \ln \sum_i \lambda_i a_i \ge \lambda_i \sum_i \ln a_i = ln \prod_i a_i^{\lambda_i} , </cmath> | <cmath> \ln \sum_i \lambda_i a_i \ge \lambda_i \sum_i \ln a_i = ln \prod_i a_i^{\lambda_i} , </cmath> | ||
with equality if and only if all the <math>a_i</math> are equal. | with equality if and only if all the <math>a_i</math> are equal. | ||
Line 15: | Line 15: | ||
<cmath> \sum_i \lambda_i a_i \ge \prod_i a_i^{\lambda_i}, </cmath> | <cmath> \sum_i \lambda_i a_i \ge \prod_i a_i^{\lambda_i}, </cmath> | ||
with equality if and only if all the <math>a_i</math> are equal, as desired. <math>\blacksquare</math> | with equality if and only if all the <math>a_i</math> are equal, as desired. <math>\blacksquare</math> | ||
+ | |||
+ | === Alternate Proof by Convexity === | ||
+ | |||
+ | ''This proof is due to [[G. Pólya]].'' | ||
+ | |||
+ | Note that the function <math>f:x \mapsto e^x</math> is strictly convex. Let <math>g(x)</math> be the line tangent to <math>f</math> at <math>(0,1)</math>; then <math>g(x) = x+1</math>. Since <math>f</math> is also a [[continuous]], [[differentiable]] function, it follows that <math>f(x) \ge g(x)</math> for all <math>x</math>, with equality exactly when <math>x=0</math>, i.e., | ||
+ | <cmath> 1+x \le e^x, </cmath> | ||
+ | with equality exactly when <math>x=0</math>. | ||
+ | |||
+ | Now, set | ||
+ | <cmath> r_i = a_i/\biggl( \sum_{j=1}^n \lambda_j a_j \biggr) - 1, </cmath> | ||
+ | for all integers <math>1\le i \le n</math>. Our earlier bound tells us that | ||
+ | <cmath> r_i +1 \le \exp(r_i), </cmath> | ||
+ | so | ||
+ | <cmath> (r_i +1)^{\lambda_i} \le \exp(\lambda_i r_i) .</cmath> | ||
+ | Multiplying <math>n</math> such inequalities gives us | ||
+ | <cmath> \frac{\prod_{i=1}^n a_i^{\lambda_i}}{ \sum_{i=1}^n \lambda_i r_i} = \prod_{i=1}^n (r_i + 1) \le \prod_{i=1}^n \exp \lambda_i r_i = \exp \sum_{i=1}^n \lambda_i a_i / \sum_{j=1}^n \lambda_j a_j - \lambda_i = \exp 0 = 1 ,</cmath> | ||
+ | so | ||
+ | <cmath> \prod_{i=1}^n a_i^{\lambda_i} \le \sum_{i=1}^n \lambda_i r_i , </cmath> | ||
+ | as desired. Equality holds when <math>r_i</math> is always equal to zero, i.e., when <math>a_i = a_j</math> for all <math>i,j</math> such that <math>\lambda_i , \lambda_j \neq 0</math>. <math>\blacksquare</math> | ||
== Proofs of Unweighted AM-GM == | == Proofs of Unweighted AM-GM == | ||
Line 23: | Line 43: | ||
Define the <math>n</math> sequence <math>\{ r_{ij}\}_{i=1}^{n}</math> as <math>r_{ij} = \sqrt[n]{a_i}</math>, for all integers <math>1 \le i,j \le n</math>. Evidently these sequences are similarly sorted. Then by the [[Rearrangement Inequality]], | Define the <math>n</math> sequence <math>\{ r_{ij}\}_{i=1}^{n}</math> as <math>r_{ij} = \sqrt[n]{a_i}</math>, for all integers <math>1 \le i,j \le n</math>. Evidently these sequences are similarly sorted. Then by the [[Rearrangement Inequality]], | ||
− | <cmath> \sum_i a_i = \sum_i \prod_j r_{ij} \ge \sum_i \prod_j | + | <cmath> \sum_i a_i = \sum_i \prod_j r_{ij} \ge \sum_i \prod_j r_{i,i+j} = n \prod_i \sqrt[n]{a_i} , </cmath> |
where we take our indices modulo <math>n</math>, with equality exactly when all the <math>r_{ij}</math>, and therefore all the <math>a_i</math>, are equal. Dividing both sides by <math>n</math> gives the desired inequality. <math>\blacksquare</math> | where we take our indices modulo <math>n</math>, with equality exactly when all the <math>r_{ij}</math>, and therefore all the <math>a_i</math>, are equal. Dividing both sides by <math>n</math> gives the desired inequality. <math>\blacksquare</math> | ||
+ | |||
+ | === Proof by Cauchy Induction === | ||
+ | |||
+ | We first prove that the inequality holds for two variables. Note that <math>(\sqrt{a}, \sqrt{b}), (\sqrt{a}, \sqrt{b})</math> are similarly sorted sequences. Then by the Rearrangement Inequality, | ||
+ | <cmath> \sqrt{ab} = \frac{ \sqrt{a} \sqrt{b} + \sqrt{b} \sqrt{a}}{2} \le \frac{ \sqrt{a} \sqrt{a} + \sqrt{b} \sqrt{b}}{2} = \frac{a+b}{2} , </cmath> | ||
+ | with equality exactly when <math>a=b</math>. | ||
+ | |||
+ | We next prove that if the inequality holds for <math>n</math> variables (with equality when all are equal to zero), than it holds for <math>2n</math> variables (with equality when all are equal to zero). Indeed, suppose the inequality holds for <math>n</math> variables. Let <math>A_n, A'_n, A_{2n}</math> denote the arithmetic means of <math>(a_1, \dotsc, a_n)</math>, <math>(a_{n+1}, \dotsc, a_{2n})</math>, <math>(a_1, \dotsc, a_{2n})</math>, respectively; let <math>G_n, G'_n, G_{2n}</math> denote their respective geometric means. Then | ||
+ | <cmath> G_{2n} = \sqrt{G_n G'_n} \le \frac{G_n + G'_n}{2} \le \frac{A_n + A'_n}{2} = A_2n, </cmath> | ||
+ | with equality when all the numbers <math>a_1, \dotsc, a_{2n}</math> are equal, as desired. | ||
+ | |||
+ | These two results show by induction that the theorem holds for <math>n=2^k</math>, for all integers <math>k</math>. In particular, for every integer <math>n</math>, there is an integer <math>N >n</math> such that the theorem holds for <math>N</math> variables. | ||
+ | |||
+ | Finally, we show that if <math>N>n</math> and the theorem holds for <math>N</math> variables, then it holds for <math>n</math> variables <math>a_1, \dotsc, a_n</math> with arithmetic mean <math>A_n</math> and geometric mean <math>G_n</math>. Indeed, set <math>b_k = a_k</math> for <math>1\le k \le n</math>, and let <math>b_k = A_k</math> for <math>n < k \le N</math>. Then | ||
+ | <cmath> G_k^{n/N} \cdot A_k^{(N-n)/N} = \prod_{i=1}^N b_i^{1/N} \le \sum_{i=1}^N b_i/N = A_n . </cmath> | ||
+ | It follows that <math>G_k^{n/N} \le A_k^{n/N}</math>, or <math>G_n \le A_n</math>, with equality exactly when all the <math>a_i</math> are equal to <math>A_k</math>. | ||
+ | |||
+ | The last two results show that for all positive integers <math>n</math>, the theorem holds for <math>n</math> variables. Therefore the theorem is true. <math>\blacksquare</math> | ||
+ | |||
+ | [[Category:Inequality]] |
Revision as of 21:50, 31 December 2007
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 right 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 so as desired. Equality holds when is always equal to zero, i.e., when for all such that .
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.