Proofs of AM-GM inequality

Question

The arithmetic - geometric mean inequality states that $$\frac{x_1+ \ldots + x_n}{n} \geq \sqrt[n]{x_1 \cdots x_n}$$ I'm looking for some original proofs of this inequality. I can find the usual proofs on the internet but I was wondering if someone knew a proof that is unexpected in some way. e.g. can you link the theorem to some famous theorem, can you find a non-trivial geometric proof (I can find some of those), proofs that use theory that doesn't link to this inequality at first sight (e.g. differential equations …)?

Induction, backward induction, use of Jensen inequality, swapping terms, use of Lagrange multiplier, proof using thermodynamics (yeah, I know, it's rather some physical argument that this theorem might be true, not really a proof), convexity, … are some of the proofs I know.

Answer 1

As requested by dani_s, I will give the thermodynamic proof of the AM-GM inequality. This is certainly an example of an original proof, although you might argue about whether or not it's rigorous.

Let's start with a list of numbers $x_i$ for which we want to prove the inequality. Take $n$ identical heat reservoirs with the same heat capacity $c$. Reservoir $i$ had initial temperature $x_i$. Bring those reservoirs in contact with each other such that this system evolves to an equilibrium temperature A.

The first law of thermodynamics (conservation of energy) implies that A equals the arithmetic mean of the $x_i$, AM.

The second law of thermodynamics states that the entropy increases until the equilibrium is reached, where the entropy has a maximum. The corresponding formula of change in entropy is $$\Delta S=c \ln{\frac{T}{T_0}}$$ where $c$ is the heat capacity, $T_0$ the initial temperature and $T$ the end temperature.

In our case $T_i=A$ for all $i$ and $T_{0,i}=x_i$. The total entropy didn't decrease and therefore, $$\sum_{i=1}^n c \ln\frac{A}{x_i} \geq 0$$

By writing the sum of logarithms as a logarithm of a product, we recognize the geometric mean. Therefore (since $A=AM$): $$\frac{AM^n}{GM^n} \geq 1$$ This proves the AM-GM inequality.

Answer 2

This is a fairly old answer of mine with a proof that was not very motivated, so I thought I'd update it with some geometric intuition about convexity, which is a good way to understand some inequalities (including Hölder's Inequality, with Cauchy–Schwarz Inequality as a special case).

Consider for simplicity the two-variable case $(x+y)/2 \ge \sqrt{xy}$:

I'm not sure if it comes across in the diagram, but the arithmetic mean will always produce a flat linear plane while the geometric mean will always produce this concave squareroot-like curvy surface which curves downward. Equality is only achieved precisely when $x = y$ and similarly in higher dimensions. The "curve downward" part shows intuitively why the inequality is true for all other values.

Here's a slice view with fixed $y=1$:

Obviously a plot is not a proof but it does give a useful visual.

The proof for more than two variables presented requires elementary properties of logarithms, which uses a common trick using log to transform dealing with multiplication to dealing with addition, which is linear. Starting off with the original statement:

$$ \frac{x_1 + \dots + x_n}{n}\ge (x_1 \dots x_n)^{1/n} $$

Taking logs preserves the inequality since $\log$ is an increasing function:

$$\iff \log \left(\frac{x_1 + \dots + x_n}{n}\right) \ge \frac 1 n \log (x_1 \dots x_n) = \frac{\log x_1 + \dots + \log x_n}{n}$$

$\DeclareMathOperator{\E}{E}$ If we write $\E[X]$ as the mean of $x_i$'s and $\E[\log(X)]$ as the mean of $\log x_i$'s, we can also understand this in the language of expectation:

$$\log(\E[X]) \ge \E[\log (X)]$$

Using the concavity of $\log$, by Jensen's Inequality (proved inductively starting from the definition of convexity, going back to the linearity of expectation, which ultimately comes from addition), the inequality holds.

---

Original post of Pólya's Proof, using similar ideas of convexity of $e^x$:

Let $f(x) = e^{x-1}-x$. The first derivative is $f'(x)=e^{x-1}-1$ and the second derivative is $f''(x) = e^{x-1}$.

$f$ is convex everywhere because $f''(x) > 0$, and has a minimum at $x=1$. Therefore $x \le e^{x-1}$ for all $x$, and the equation is only equal when $x=1$.

Using this inequality we get

$$\frac{x_1}{a} \frac{x_2}{a} \cdots \frac{x_n}{a} \le e^{\frac{x_1}{a}-1} e^{\frac{x_2}{a}-1} \cdots e^{\frac{x_n}{a}-1}$$

with $a$ being the arithmetic mean. The right side simplifies

$$\exp \left(\frac{x_1}{a} -1 \ +\frac{x_1}{a} -1 \ + \cdots + \frac{x_n}{a} -1 \right)$$

$$=\exp \left(\frac{x_1 + x_2 + \cdots + x_n}{a} - n \right) = \exp(n - n) = e^0 = 1$$

Going back to the first inequality

$$\frac{x_1x_2\cdots x_n}{a^n} \le 1$$

So we end with

$$\sqrt[n]{x_1x_2\cdots x_n} \le a$$

Answer 3

As $(\sqrt{x_1}-\sqrt{x_2})^2 \geq 0$ we have $$\sqrt{x_1 \cdot x_2} \leq \frac{x_1+x_2}{2}.$$ Applying this inequality twice, we get $$(x_1 x_2 x_3 x_4)^{\frac{1}{4}} \leq \frac{\sqrt{x_1 x_2}+\sqrt{x_3 x_4}}{2} \leq \frac{x_1+x_2+x_3+x_4}{4}.$$ By induction, it is not difficult to see that $$(x_1 \cdots x_{2^k})^{\frac{1}{2^k}} \leq \frac{x_1+\ldots+x_{2^k}}{2^k} \tag{1}$$ for all $k \geq 1$.

It remains to fill the gaps between the powers of two. So let $x_1,\ldots,x_n$ be arbitrary positive numbers and choose $k$ such that $n\leq 2^k$. We set

$$\alpha_i := \begin{cases} x_i & i \leq n \\ A & n< i \leq 2^k \end{cases}$$

where $A:= \frac{x_1+\ldots+x_n}{n}$. Applying $(1)$ to the $(\alpha_1,\ldots,\alpha_{2^k})$ yields

$$\bigg( x_1 \ldots x_n A^{2^k-n} \bigg)^{\frac{1}{2^k}} \leq \frac{x_1+\ldots+x_n+(2^k-n) A}{2^k} = A.$$

Hence,

$$(x_1 \ldots x_n)^{1/n} \leq A = \frac{x_1+\ldots+x_n}{n}.$$

Answer 4

Bernoulli's Inequality says that for $u\ge-1$ and $0\le r\le1$, $$ (1+u)^r\le1+ru\tag{1} $$ Setting $u=\frac xy-1$ in $(1)$ says that for $x,y\gt0$, $$ \left(\frac xy\right)^r\le(1-r)+r\frac xy\tag{2} $$ If we multiply $(2)$ by $y$, we get $$ x^ry^{1-r}\le rx+(1-r)y\tag{3} $$ Now $(3)$ can be used inductively to get $$ x_1^{r_1}x_2^{r_2}x_3^{r_3}\dots x_n^{r_n}\le r_1x_1+r_2x_2+r_3x_3+\dots+r_nx_n\tag{4} $$ where $r_1,r_2,r_3,\dots,r_n\ge0$ and $r_1+r_2+r_3+\dots+r_n=1$.

Inductive step:

Suppose that $(4)$ holds, then we can use $(3)$ to get $$ \begin{align} &\left(x_1^{r_1}x_2^{r_2}x_3^{r_3}\dots x_n^{r_n}\right)^{1-r_{n+1}}x_{n+1}^{r_{n+1}}\\ &\le(1-r_{n+1})\left(r_1x_1+r_2x_2+r_3x_3+\dots+r_nx_n\right)+r_{n+1}x_{n+1}\tag{5} \end{align} $$ where $(1-r_{n+1})(r_1+r_2+r_3+\dots+r_n)+r_{n+1}=1$

Answer 5

This is a plausibility argument rather than a complete proof. Without loss of generality we may assume that $x_1,x_2,\dots,x_n\in[0,1].$ Let $p_i=x_i^{1/n}\in[0,1].$

Consider the following variant of Russian Roulette. You are faced with a panel of $n$ buttons. If you press the $i^{\text{th}}$ button, then with probability $p_i$ you will get a fatal electric shock. You are required to press a button $n$ times. The probabilities $p_1,\dots,p_n$ are known to you, but the buttons are not labeled, you don't know which is which. You can choose between two strategies.

I. Press each button once.

II. Choose a button at random and press it $n$ times.

It is INTUITIVELY OBVIOUS that strategy II is better: you have a better chance of survival pressing the same button that you already pressed and lived, than pressing an untried button. (Prove this rigorously and you have a proof of the AM-GM inequality.)

Now, the probability of survival with strategy I is $$p_1p_2\cdots p_n=(x_1x_2\cdots x_n)^{1/n}$$ and with strategy II it's $$\frac{p_1^n+p_2^n+\cdots+p_n^n}n=\frac{x_1+x_2+\cdots+x_n}n,$$ so the fact that strategy II dominates strategy I is expressed by the AM-GM inequality $$(x_1x_2\cdots x_n)^{1/n}\le\frac{x_1+x_2+\cdots+x_n}n.$$

Answer 6

My idea is to use only the Cauchy Schwartz inequality by induction.

Applying the Cauchy_Schwartz inequality on the vectors $(\sqrt{a},\sqrt{a})^T$ and $(\sqrt{b},\sqrt{b})^T$ we get: $$\sqrt{ab} +\sqrt{ab} \le (a+b)^{1/2}(a+b)^{1/2} $$ that is $$\sqrt{ab} \le \frac{a+b}{2}~~~~~~\color{red}{\text{AM-GM for $n =2$}}$$

Hypothesis of induction: Assume that for all $p\in\{1,2,\cdots, n-1\}$ we have, \begin{align*} \color{blue}{(a_1a_2\cdots a_p)^{1/p}\leq \frac{a_1+a_2+\cdots+a_p}{p}} \end{align*} We want to prove that it is true for $n$. we will discuss two case: $n =2p$ and $n=2p-1$

If $n =2p$ Then we proceed as follows: Using that case: $n=2$ and the case $n=p$, we have,

$$ \begin{align}\color{blue}{\frac{a_1+a_2+\cdots+a_n}{n} }&= \frac{1}{2}\left(\overbrace{\frac{a_1+a_2+\cdots+a_p}{p}}^a+\overbrace{\frac{a_{p+1}+a_{p+2}+\cdots+a_n}{p}}^b \right) \\ &\ge\sqrt{\left(\frac{a_1+a_2+\cdots+a_p}{p}\right) \left(\frac{a_{p+1}+a_{p+2}+\cdots+a_n}{p}\right)}\\ &\ge\sqrt{(a_1a_2\cdots a_p)^{1/p}(a_{p+1}a_{p+2}\cdots a_n)^{1/p}}\\ &=\sqrt{(a_1a_2\cdots a_n)^{1/p}} = \color{blue}{(a_{p+1}a_{p+2}\cdots a_n)^{1/n} } ~~~~~~\color{red}{\text{AM-GM for $n =2p$}} \end{align}$$

If $n =2p-1$ (we use the case $n=2p$, as follows.we have, $n+1 =2p $ and $p<n$ : Then taking $$ a_{n+1} = \frac{a_1+a_2+\cdots+a_n}{n}$$ in the previous case we obtain,

\begin{align}&\frac{a_1+a_2+\cdots+a_{n+1}}{n+1} \ge (a_1a_2\cdots a_{n+1})^{\frac{1}{n+1}}\\ &\Longleftrightarrow\frac{1}{n+1}\left(a_1+a_2+\cdots+a_n+\overbrace{\frac{a_1+a_2+\cdots+a_n}{n}}^{a_{n+1}} \right) \ge \left(a_1a_2\cdots a_{n}\left(\overbrace{\frac{a_1+a_2+\cdots+a_n}{n}}^{a_{n+1}}\right) \right)^{\frac{1}{n+1}}\\ \\&\Longleftrightarrow\frac{a_1+a_2+\cdots+a_n}{n} \ge \left(a_1a_2\cdots a_{n}\left(\frac{a_1+a_2+\cdots+a_n}{n}\right) \right)^{\frac{1}{n+1}}\\ &\Longleftrightarrow\left(\frac{a_1+a_2+\cdots+a_n}{n}\right)^{\frac{n}{n+1}} \ge \left(a_1a_2\cdots a_{n}\right)^{\frac{1}{n+1}} \\&\Longleftrightarrow \color{blue}{\frac{a_1+a_2+\cdots+a_n}{n} \ge \left(a_1a_2\cdots a_{n}\right)^{\frac{1}{n}}}~~~~\color{red}{\text{AM-GM for $n =2p-1$}}\end{align}

Answer 7

An alternate proof for the case $n=3$: it is equivalent to show that $a^3+b^3+c^3-3abc \geq 0$ for positive reals.

$$\begin{align} a^3+b^3+c^3 - 3abc & = \\ c^3 + (a+b)^3 -3ab(a+b)-3abc & = \\ c^3 + (a+b)^3 - 3ab(a+b+c) & = \\ (a+b+c)^3 - 3c(a+b)(a+b+c) - 3ab(a+b+c) & = \\ (a+b+c)^3 - 3(ab+ac+bc)(a+b+c) & = \\ (a+b+c) \cdot ((a+b+c)^2 - 3(ab+ac+bc)) & = \\ (a+b+c) \cdot ((a^2+b^2+c^2) - (ab+ac+bc)) & = \\ (a+b+c) \cdot \cfrac{(a-b)^2+(b-c)^2+(c-a)^2}{2} \end{align}$$

And it is obviously true.

(P.S.: we can use the same technique of transfinite induction from here too!)

Answer 8

Another answer. We can prove this alternative result:

If $a_1, \ldots, a_n$ are positive reals such that $a_1 + \dots + a_n = n$, then $a_1 \dots a_n \leq 1$.

We can suppose wlog that $a_1 \leq \dots \leq a_n$.

Notice that we can suppose $a_n \not= 1$, or else we could just solve the same problem for $n-1$.

By "pigeonhole principle", we know that $a_1 \leq 1 \leq a_n$. If we change them by their arithmetical mean, the sum stays the same, but the product increases. Indeed, the product "increases" by $(\frac{a_1+a_n}{2})^2-a_1a_n = (\frac{a_1-a_n}{2}) \geq 0$, with equality if and only if $a_1=a_n$.

That way, we can always increase the sum whenever there are at least two different terms. The only way it can't be done is if all terms are equal; and this is the supremum value.

(Another possible solution would be change $a_n$ by $1$ and $a_1$ by $(a_1+a_n)-1$; the sum stays the same but the product "increases" by $a_1+a_n-1-a_1a_n = (1-a_1)(a_n-1) \geq 0$; that way the maximum occurs if all terms are $1$).

Answer 9

AM-GM inequality says that for any $ a_1, \dots , a_n > 0 $, we have $ \dfrac{a_1 + \cdots + a_n}{n} \geq \sqrt[n]{a_1 \cdots a_n} $ with equality holding if and only if $ a_1 = \cdots = a_n $.

Here is Cauchy's Backward Induction proof, but with the backward part slightly modified (and hopefully more intuitive). We'll first prove the inequality, and then think about when equality holds. For brevity, let $ P_n $ mean "For any $a_1, \dots a_n > 0, \dfrac{a_1 + \cdots + a_n}{n} \geq \sqrt[n]{a_1 \cdots a_n}$ ".

$P_1$ holds trivially. $P_2$ is true because $ \dfrac{a_1 + a_2}{2} \geq \sqrt{a_1 a_2} $ can be written as $ a_1 + a_2 - 2\sqrt{a_1 a_2} \geq 0 $, which is just $ (\sqrt{a_1} - \sqrt{a_2})^2 \geq 0 $. $ P_4 $ comes from $ P_2 $, as $ \dfrac{a_1 + a_2 + a_3 + a_4}{4} = \dfrac{\dfrac{a_1 + a_2}{2} + \dfrac{a_3 + a_4}{2}}{2} \geq \dfrac{\sqrt{a_1 a_2} + \sqrt{a_3 a_4}}{2} \geq \sqrt{\sqrt{a_1 a_2}\sqrt{a_3 a_4}} = \sqrt[4]{a_1 \cdots a_4} $. Similarly $P_8$ comes from $P_4$, $P_{16}$ comes from $P_8$, etc. In general, if we know a $ P_{2^k} $ holds then $ P_{2^{k+1}} $ must hold as $ \dfrac{ a_1 + \cdots +a_{2^{k+1}} }{2^{k+1}} = \dfrac{ \dfrac{ a_1 + \cdots a_{2^k} }{2^k} + \dfrac{ a_{2^{k} + 1} + \cdots a_{2^{k+1}} }{2^k} }{2} \geq \dfrac{(a_1 \cdots a_{2^k})^{ \frac{1}{2^k} } + (a_{2^k + 1} \cdots a_{2^{k+1}})^{ \frac{1}{2^k} } }{2} \geq \sqrt{ (a_1 \cdots a_{2^k})^{ \frac{1}{2^k} } (a_{2^k + 1} \cdots a_{2^{k+1}})^{ \frac{1}{2^k} } } = (a_1 \cdots a_{2^{k+1}})^{\frac{1}{2^{k+1}}} $.

So it is clear $P_k$ holds whenever $ k $ is a power of $2$.

It now suffices to show "If a $P_{k+1}$ holds, then $P_k$ must hold". [Informally, we showed we can jump to powers of $2$, but there are gaps so now we are trying to show we can also take single steps backwards]. So we'll try to prove this:

Fix any $ a_1, \dots, a_k > 0 $. Now we are to show $ \dfrac{a_1 + \cdots + a_k}{k} \geq (a_1 \cdots a_k)^{\frac{1}{k}} $ , but we have the information $ \dfrac{ a_1 + \cdots + a_k + t }{k+1} \geq (a_1 \cdots a_k t)^{\frac{1}{k+1}} $ for any $ t > 0 $. In order to match the info's RHS to that of the goal we can try picking a $ t $ such that $ (a_1 \cdots a_k t)^{\frac{1}{k+1}} = (a_1 \cdots a_k)^{\frac{1}{k}} $, i.e we can try setting $ t = (a_1 \cdots a_k)^{\frac{1}{k}} $, and in fact it works : $ \dfrac{ a_1 + \cdots a_k + (a_1 \cdots a_k)^{\frac{1}{k}} }{k+1} \geq (a_1 \cdots a_k)^{\frac{1}{k}} $, giving the required inequality $ \dfrac{a_1 + \cdots + a_k}{k} \geq (a_1 \cdots a_k)^{\frac{1}{k}} $. [We could've also tried to match info's LHS to that of the goal, i.e we could've tried setting $ t = \dfrac{a_1 + \cdots a_k}{k} $, and even this happens to work !].

So the inequality part is proved. Now we'll think about when the equality is true. The $P_2$-inequality becomes equality if and only if $ \sqrt{a_1} - \sqrt{a_2} = 0 $, i.e if and only it $ a_1 = a_2 $. The $P_4$-inequality becomes equality if and only if $ \sqrt{a_1 a_2} = \sqrt{a_3 a_4}, a_1 = a_2 $ and $ a_3 = a_4 $, i.e. if and only if $ a_1 = \cdots = a_4 $. Proceeding so, it is clear $P_{2^k}$-inequality becomes equality if and only if $ a_1 = \cdots = a_{2^k} $. Now looking at the backwards induction step above, we see that in general equality holds if and only if all the numbers taken are equal.

Answer 10

We use the method if infinite descent.

Let $P_n$ be the proposition that there is some set $S_n=\{a_1,a_2,\dots a_n\}$ with $a_i\geqslant0$ and $\sum a_i=n$ and for which $\prod a_i > 1$.

We would like to show that $P_n$ is always false. Suppose, for the sake of contradiction, that there is some $n$ for which $P_n$ is true and let $m$ be the smallest such $n$.

Clearly $P_1$ is false and so $m \geqslant 2$.

In order for $\sum a_i=n$ there must be at least one element bigger than $1$ and one less than $1$ (they cannot all equal $1$ because $\prod a_i > 1$) so we can say $a_1>1$ and $a_2<1$.
$$(a_1-1)(1-a_2)>0 \implies a_1+a_2-1 >a_1 a_2 \tag 1$$

We now replace $a_1$ with $a_1+a_2-1$ and $a_2$ with $1$. The sum ($\sum a_i$) doesn't change and, by (1), the product increases, so we still have $\prod a_i > 1$.

But now one of the elements of $S_m$ is equal to $1$ we can define $S_{m-1}=S_m \setminus \{1\}$ and for this set we have $\sum a_i=m-1$ and $\prod a_i > 1$. This proves $P_{m-1}$ and so contradicts the definition of $m$ and so our assumption that such an $m$ exists must be false and so $P_n$ is false for all $n$.

With the hard work done, AM-GM follows immediately. Suppose

$$\frac{x_1+ \cdots + x_n}{n} < \sqrt[n]{x_1 \cdots x_n}$$

Then define

$$a_i = \frac{n \, x_i}{x_1+ \cdots + x_n}$$

This would prove $P_n$ which we have shown to be false and so no such inequality can be true.