How to show AM-GM inequality using rearrangement inequality?

1,028

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:

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:

Share:
1,028

Related videos on Youtube

Martin Sleziak
Author by

Martin Sleziak

Updated on August 01, 2022

Comments

  • Martin Sleziak
    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
      lulu over 7 years
      Here's a relevant link.
    • Martin R
      Martin R over 7 years
    • DanielWainfleet
      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
      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
      DanielWainfleet over 7 years
      Right . 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
    ZFR about 3 years
    Really nice proof! +1