# Difference between revisions of "Proofs of AM-GM"

This pages lists some proofs of the weighted AM-GM Inequality. The inequality's statement is as follows: for all nonnegative reals $a_1, \dotsc, a_n$ and nonnegative reals $\lambda_1, \dotsc, \lambda_n$ such that $\sum_{i=1}^n \lambda_i = 1$, then $$\sum_{i=1}^n \lambda_i a_i \ge \prod_{i=1}^n a_i^{\lambda_i},$$ with equality if and only if $a_i = a_j$ for all $i,j$ such that $\lambda_i, \lambda_j \neq 0$.

We first note that we may disregard any $a_i$ for which $\lambda_i= 0$, as they contribute to neither side of the desired inequality. We also note that if $a_i= 0$ and $\lambda_i \neq 0$, for some $i$, 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 $a_j = 0 = a_i$ whenever $\lambda_j\neq 0$. Thus we may henceforth assume that all $a_i$ and $\lambda_i$ are strictly positive.

## Complete Proofs

### Proof by Convexity

We note that the function $x \mapsto \ln x$ is strictly concave. Then by Jensen's Inequality, $$\ln \sum_i \lambda_i a_i \ge \sum_i \lambda_i \ln a_i = \ln \prod_i a_i^{\lambda_i} ,$$ with equality if and only if all the $a_i$ are equal. Since $x \mapsto \ln x$ is a strictly increasing function, it then follows that $$\sum_i \lambda_i a_i \ge \prod_i a_i^{\lambda_i},$$ with equality if and only if all the $a_i$ are equal, as desired. $\blacksquare$

### Alternate Proof by Convexity

This proof is due to G. Pólya.

Note that the function $f:x \mapsto e^x$ is strictly convex. Let $g(x)$ be the line tangent to $f$ at $(0,1)$; then $g(x) = x+1$. Since $f$ is also a continuous, differentiable function, it follows that $f(x) \ge g(x)$ for all $x$, with equality exactly when $x=0$, i.e., $$1+x \le e^x,$$ with equality exactly when $x=0$.

Now, set $$r_i = a_i/\biggl( \sum_{j=1}^n \lambda_j a_j \biggr) - 1,$$ for all integers $1\le i \le n$. Our earlier bound tells us that $$r_i +1 \le \exp(r_i),$$ so $$(r_i +1)^{\lambda_i} \le \exp(\lambda_i r_i) .$$ Multiplying $n$ such inequalities gives us

$$\prod_{i=1}^n (r_i + 1)^{\lambda_{i}} \le \prod_{i=1}^n \exp \lambda_i r_i$$

Evaluating the left hand side:

$$\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 } ,$$

for

$$\sum_{j=1}^n \lambda_i = 1 .$$

Evaluating the right hand side:

$$\prod_{i=1}^n \exp \lambda_i r_i = \prod_{i=1}^n \exp \left(\frac{a_i \lambda_i}{ \sum_{i=1}^n \lambda_j a_j} - \lambda_i\right) = \exp \left(\frac{\sum_{i=1}^n a_i \lambda_i}{ \sum_{i=1}^n \lambda_j a_j} - \sum_{i=1}^n \lambda_i\right) = \exp 0 = 1 .$$

Substituting the results for the left and right sides:

$$\frac{\prod_{i=1}^n a_i^{\lambda_i} }{ \sum_{j=1}^n \lambda_j a_j } \le 1$$

$$\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 ,$$

as desired. $\blacksquare$

## Proofs of Unweighted AM-GM

These proofs use the assumption that $\lambda_i = 1/n$, for all integers $1 \le i \le n$.

### Proof by Rearrangement

Define the $n$ sequence $\{ r_{i,j}\}_{i=1}^{n}$ as $r_{i,j} = \sqrt[n]{a_i}$, for all integers $1 \le i,j \le n$. Evidently these sequences are similarly sorted. Then by the Rearrangement Inequality, $$\sum_i a_i = \sum_i \prod_j r_{i,j} \ge \sum_i \prod_j r_{i+j,j} = n \prod_i \sqrt[n]{a_i} ,$$ where we take our indices modulo $n$, with equality exactly when all the $r_{i,j}$, and therefore all the $a_i$, are equal. Dividing both sides by $n$ gives the desired inequality. $\blacksquare$

### Proof by Cauchy Induction

We first prove that the inequality holds for two variables. Note that $(\sqrt{a}, \sqrt{b}), (\sqrt{a}, \sqrt{b})$ are similarly sorted sequences. Then by the Rearrangement Inequality, $$\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} ,$$ with equality exactly when $a=b$.

We next prove that if the inequality holds for $n$ variables (with equality when all are equal to zero), than it holds for $2n$ variables (with equality when all are equal to zero). Indeed, suppose the inequality holds for $n$ variables. Let $A_n, A'_n, A_{2n}$ denote the arithmetic means of $(a_1, \dotsc, a_n)$, $(a_{n+1}, \dotsc, a_{2n})$, $(a_1, \dotsc, a_{2n})$, respectively; let $G_n, G'_n, G_{2n}$ denote their respective geometric means. Then $$G_{2n} = \sqrt{G_n G'_n} \le \frac{G_n + G'_n}{2} \le \frac{A_n + A'_n}{2} = A_{2n},$$ with equality when all the numbers $a_1, \dotsc, a_{2n}$ are equal, as desired.

These two results show by induction that the theorem holds for $n=2^k$, for all integers $k$. In particular, for every integer $n$, there is an integer $N >n$ such that the theorem holds for $N$ variables.

Finally, we show that if $N>n$ and the theorem holds for $N$ variables, then it holds for $n$ variables $a_1, \dotsc, a_n$ with arithmetic mean $A_n$ and geometric mean $G_n$. Indeed, set $b_k = a_k$ for $1\le k \le n$, and let $b_k = A_n$ for $n < k \le N$. Then $$G_n^{n/N} \cdot A_n^{(N-n)/N} = \prod_{i=1}^N b_i^{1/N} \le \sum_{i=1}^N b_i/N = A_n .$$ It follows that $G_k^{n/N} \le A_k^{n/N}$, or $G_n \le A_n$, with equality exactly when all the $a_i$ are equal to $A_k$.

The last two results show that for all positive integers $n$, the theorem holds for $n$ variables. Therefore the theorem is true. $\blacksquare$

### Proof by Calculus

We will start the proof by considering the function $f(x) = \ln x - x$. We will now find the maximum of this function. We can do this simply using calculus. We need to find the critical points of $f(x)$, we can do that by finding $f'(x)$ and setting it equal to $0$. Using the linearity of the derivative $f'(x) = \frac{1}{x} - 1$. We need $f'(x) = 0$ $$f'(x) = \frac{1}{x} - 1 = 0$$ $$\frac{1}{x} = 1$$ $$x = 1$$ Note that this is the only critical point of $f(x)$. We can confirm it is the maximum by finding it's second derivative and making sure it is negative. $f''(x) = -\frac{1}{x^2}$ letting x = 1 we get $f''(1) = -\frac{1}{1} < 0$. Since the second derivative $f''(x) < 0$, $f(1)$ is a maximum. $f(1) = \ln 1 - 1 = -1$. Now that we have that $f(1) = -1$ is a maximum of $f(x)$, we can safely say that $\ln x - x \leq -1$ or in other words $\ln x \leq x - 1$. We will now define a few more things and do some manipulations with them. Let $A = \frac{\sum_{i=1}^{n} a_i}{n}$, with this notice that $nA = \sum_{i=1}^{n} a_i$. This fact will come into play later. now we can do the following, let $x = \frac{a_i}{A}$ and plug this into $\ln x < x - 1$, we get $$\ln\left(\frac{a_1}{A}\right) \leq \frac{a_1}{A} - 1$$ $$\ln\left(\frac{a_2}{A}\right) \leq \frac{a_2}{A} - 1$$ $$\vdotswithin{=}$$ $$\ln\left(\frac{a_n}{A}\right) \leq \frac{a_n}{A} - 1$$ Adding all these results together we get $$\ln\left(\frac{a_1}{A}\right) + \ln\left(\frac{a_2}{A}\right) + \dots + \ln\left(\frac{a_n}{A}\right) \leq \frac{a_1}{A} - 1 + \frac{a_2}{A} - 1 + \dots + \frac{a_n}{A} - 1$$ $$\ln\left(\frac{\prod_{i=1}^{n} a_i}{A^n}\right) \leq \frac{\sum_{i=1}^{n}a_i}{A} - n$$ $$\ln\left(\frac{\prod_{i=1}^{n} a_i}{A^n}\right) \leq \frac{nA}{A} - n$$ $$\ln\left(\frac{\prod_{i=1}^{n} a_i}{A^n}\right) \leq n - n$$ $$\ln\left(\frac{\prod_{i=1}^{n} a_i}{A^n}\right) \leq 0$$ Now exponentiating both sides we get $$e^{\ln\left(\frac{\prod_{i=1}^{n} a_i}{A^n}\right)} \leq e^{0}$$ $$\frac{\prod_{i=1}^{n} a_i}{A^n} \leq 1$$ $$\prod_{i=1}^{n} a_i \leq A^n$$ $$\sqrt[\leftroot{2}\uproot{3}n]{\prod_{i=1}^{n} a_i} \leq \sqrt[\leftroot{2}\uproot{3}n]{A^n}$$ $$\sqrt[\leftroot{2}\uproot{3}n]{\prod_{i=1}^{n} a_i} \leq A$$ $$\sqrt[\leftroot{2}\uproot{3}n]{\prod_{i=1}^{n} a_i} \leq \frac{\sum_{i=1}^{n} a_i}{n}$$ This proves the AM-GM inequality. $\blacksquare$

### Alternate Proof by Induction

Because $(a-b)^2$ is a square, $(a-b)^2\geq 0$. Now, through algebra: $$a^2-2ab+b^2 \geq 0$$ $$a^2+2ab+b^2 \geq 4ab$$ $$\frac{(a+b)^2}4 \geq ab$$ $$\frac{a+b}2 \geq \sqrt{ab}$$ From here, we proceed with induction through the second paragraph of the above proof with Cauchy Induction to show the theorem is true. $\blacksquare$