How to show AM-GM inequality using rearrangement inequality?
Solution 1
Here is the proof of AM-GM based on rearrangement inequality following the hints given in Steele J.M. The Cauchy-Schwarz master class (MAA CUP 2004), Exercise 5.7, page 84. (And the same proof can be certainly found in many other places.)
We first show that:
For any $c_1,\dots,c_n>0$ we have $$n\le \frac{c_1}{c_n}+\frac{c_2}{c_1}+\frac{c_3}{c_2}+\dots+\frac{c_n}{c_{n-1}}. \tag{1}$$
Indeed, if the permutation which reorders these $n$ numbers in the increasing order is $\sigma \colon \{1,2,\dots,n\}\to\{1,2,\dots,n\}$ then we have \begin{gather*} c_{\sigma(1)} \le c_{\sigma(2)} \le \dots \le c_{\sigma(n-1)} \le c_{\sigma(n)}\\ \frac1{c_{\sigma(n)}} \le \frac1{c_{\sigma(n-1)}} \le \dots \le \frac1{c_{\sigma(2)}} \le \frac1{c_{\sigma(1)}} \end{gather*} and the rearrangement inequality gives us $$c_1\cdot \frac1{c_n} + c_2\cdot\frac1{c_1} + \dots + c_n \frac1{c_{n-1}} \ge c_{\sigma(1)}\cdot\frac1{c_{\sigma(1)}}+c_{\sigma(2)}\cdot\frac1{c_{\sigma(2)}}+\dots+c_{\sigma(n)}\cdot\frac1{c_{\sigma(n)}}=n.$$
Simply by using $(1)$ for $c_n=x_1, c_2=x_1x_2, c_3=x_1x_2x_3, \dots, c_n=x_1x_2\cdots x_n$ we get:
For any $x_1,x_2,\dots,x_n>0$ we have $$n\le \frac{x_1}{x_1x_2\dots x_n}+x_2+x_3+\dots+x_n. \tag{2}$$
Making one more substitution, namely replacing $x_i$ by $ax_i$, we get that
For any $x_1,x_2,\dots,x_n>0$ and $a>0$ we have $$n\le \frac{ax_1}{a^nx_1x_2\dots x_n}+ax_2+ax_3+\dots+ax_n. \tag{3}$$
Now if we choose $a$ in $(3)$ in such way that $a^nx_1x_2\dots x_n=1$, i.e., $a=\dfrac1{\sqrt[n]{x_1x_2\dots x_n}}$, then the above equality becomes
\begin{align*} n &\le a(x_1+x_2+\dots+x_n)\\ \frac1a &\le \frac{x_1+x_2+\dots+x_n}n\\ \sqrt[n]{x_1x_2\dots x_n} &\le \frac{x_1+x_2+\dots+x_n}n \end{align*} So we get that AM-GM is true for any positive real numbers $x_1,x_2,\dots,x_n$.
Solution 2
Maybe it might be useful to make also a CW post collecting some references where the proofs of AM-GM based on rearrangement inequality can be found. (Feel free to add more.)
Online:
- Rearrangement Inequality - A Problem Solver's Paradise at AoPS
- Rearrangement Inequality at IMOMath. (Only the proof for $n=4$ is given here. But it seems that the generalization to arbitrary $n$ would be straightforward - although perhaps not that easy to write down formally. Which might be the reason for choosing a specific case, in order to illustrate the method more clearly.)
- Yue Kwok Choy: Rearrangement Inequality
Books:
- R. B. Manfrino et al. Inequalities: A Mathematical Olympiad Approach, Exercise 1.70. The book also contains solution for this exercise.
- Steele J.M. The Cauchy-Schwarz master class (MAA CUP 2004), Exercise 5.7, page 84
Searches:
In general, it is not easy to search for formulas, inequalities, proofs (or anything involving variables and mathematical expressions). But in this case both inequalities have names, so there are some reasonable choices:
Related videos on Youtube
Martin Sleziak
Updated on August 01, 2022Comments
-
Martin Sleziak over 1 year
Wikipedia article on Rearrangement inequality (link to the current revision) says (without giving any citation for this claim):
Many famous inequalities can be proved by the rearrangement inequality, such as the arithmetic mean – geometric mean inequality, the Cauchy–Schwarz inequality, and Chebyshev's sum inequality.
How can the inequality of arithmetic and geometric mean be shown using rearrangement inequality?
(I had a look at this post: Proofs of AM-GM inequality. I did not see there a proof relying on rearrangement inequality - I hope I did not overlook it.)
-
lulu over 7 yearsHere's a relevant link.
-
Martin R over 7 yearsAlso here: emis.de/journals/BMMSS/pdf/v21n2/v21n2p8.pdf.
-
DanielWainfleet over 7 years@lulu . In your link, in the section Theorems Derived From Re-Arrangement, there is a typo in the def'n of $a_j$. The denominator should be $c^j$, not $c^i$. Otherwise it's very clear.
-
lulu over 7 years@user254665 You are right about the typo...and in the next line they use $a_i$ instead of $a_j$ which is, at least, less than ideal notation ($a_j$ having been newly defined and $i$ having been established as the dummy indexing variable). But I do think the argument is clear.
-
DanielWainfleet over 7 yearsRight . Since $c^i$ didn't make sense, I quickly read thru it to see if $c^j$ would make the argument valid, which it does, and I missed the 2nd typo. There are many many ways to prove the AGM inequality but I haven't seen this one before.
-
-
ZFR about 3 yearsReally nice proof! +1