Rearrangement Inequality

Statement

If $ x_1 $, $ x_2 $, $ \dots $, $ x_n $ and $ y_1 $, $ y_2 $, $ \dots $, $ y_n $ are two non-decreasing sequences of real numbers, and if $ \sigma $ is any permutation of $ \{1,2,\dots, n\} $, then the following inequality holds:

$\displaystyle\sum_{i=1}^{n}x_iy_{n+1-i}\le\sum_{i=1}^{n}x_iy_{\sigma(i)}\le\sum_{i=1}^{n}x_iy_i.$

The equality holds when either one of the sequences is constant.

Two sequences that are both increasing or both decreasing are said to be similarly ordered. If one is increasing and the other is decreasing they are said to be inversely (or, oppositely) ordered. Given two sequences $x_i,$ $y_i,$ $i = 1, 2, \ldots, n,$ when it comes to evaluating $\displaystyle\sum_{i=1}^{n}x_iy_i,$ we can always assume that one of the sequences is monotone, say monotone increasing, whereas the other could be looked at as a permutation of a decreasing sequence $u_i,$ $i = 1, 2, \ldots, n,$ or a permutation of an increasing sequence $v_i,$ $i = 1, 2, \ldots, n.$ It is then possible to estimate

$\displaystyle\sum_{i=1}^{n}x_iu_i\le\sum_{i=1}^{n}x_iy_i\le\sum_{i=1}^{n}x_iv_i.$

Proof

First, we prove $\displaystyle\sum_{i=1}^{n}x_iy_i\le\sum_{i=1}^{n}x_iv_i.$ (To remind, we assume that $\{x_i\}$ and $\{v_i\}$ are both monotone increasing, with the latter being just a reodered sequence $\{y_i\}).$ The proof is by mathematical induction. The case $n=1\;$ is vacuously true. The case $n=2\;$ follows from $(x_2-x_1)(y_1-y_2)\le 0\;$ which is equivalent to $x_1y_2+x_2y_1\le x_1y_1+x_2y_2.$

Suppose the case $n = k\;$ is true. Then for the case $n = k + 1,\;$ there are two possibilities: either $y_{k+1}=v_{k+1},\;$ i.e., $y_{k+1}\;$ is the largest element in the sequence, or $y_{k+1}\lt v_{k+1}.\;$ In the former case, there is nothing to prove because, the permutation $\sigma$ leaves $y_{k+1}\;$ fixed such that the passage from the case $n=k\;$ to the case $n=k+1\;$ consists in adding $x_{k+1}y_{k+1}\;$ to both sides of the inequality, true by the inductive hypothesis.

If $y_{k+1}\lt v_{k+1}\;$ then let $y_{k+1}=v_s.\;$ The sum $\displaystyle\sum_{i=1}^{k+1}x_iy_i\;$ contains two terms: for some $t,\;$ $x_tv_{k+1}+x_{k+1}v_s\;$ which may be compared to $x_tv_s+x_{k+1}v_{k+1}.\;$ As in the case of $n=2,\;$ we have $(x_{k+1}-x_t)(v_s-v_{k+1})\le 0,\;$ implying $x_tv_{k+1}+x_{k+1}v_s \le x_tv_s+x_{k+1}v_{k+1}.\;$ Let $\{y'_i\}\;$ be the sequence $\{y_i\},\;$ with $v_{k+1}\;$ and $v_s,\;$ swapped. We then get

$\displaystyle\sum_{i=1}^{k+1}x_iy_i\le\sum_{i=1}^{k}x_iy'_i+x_{k+1}v_{k+1}\le\sum_{i=1}^{k}x_iv_i+x_{k+1}v_{k+1}=\sum_{i=1}^{k+1}x_iv_i.$

The left inequality $\displaystyle\sum_{i=1}^{n}x_iu_i\le\sum_{i=1}^{n}x_iy_i\;$ is actually equivalent to the right one: the proof of one is obtained from the proof of the other by changing signs of all the terms in sequence $\{y_i\}.$

Example 1 (The AM-GM inequality)

Let's derive the AM-GM inequality by rearrangement. We want to show that,for positive $\{a_i\},$

$\displaystyle\frac{1}{n}(a_1+a_2+\ldots+a_n)\ge\sqrt[n]{a_1\cdot a_2\cdot\ldots\cdot a_n}.$

Define $c=\sqrt[n]{a_1\cdot a_2\cdot\ldots\cdot a_n};\;$ $\displaystyle x_1=\frac{a_1}{c},\;$ $\displaystyle x_2=\frac{a_1a_2}{c^2},\;$ $\displaystyle x_3=\frac{a_1a_2a_3}{c^3},\ldots\;$ and $\displaystyle u_i=\frac{1}{x_i}.\;$ Note that $\displaystyle x_n=\frac{a_1\cdot\ldots\cdot a_n}{c^n}=1\;$ and so too $\displaystyle u_n=\frac{1}{x_n}=1.\;$ The sequences $\{x_i\}\;$ and $\{u_i\}\;$ are oppositely ordered, therefore,

$x_1u_1+x_2u_2+\ldots+x_nu_n\le x_1u_n+x_2u_{n-1}+\ldots+x_nu_1.$

In other words,

$\displaystyle n=1+1+\ldots+1\le \frac{x_1}{c}+\frac{x_2}{c}+\ldots+\frac{x_n}{c}.$

which is exactly the AM-GM inequality.

Example 2 (Nesbitt's inequality & generalization)

Let $\{a_i\}\;$ be a sequence of positive numbers and $s=a_1+\ldots+a_n.\;$ Then

$\displaystyle\frac{a_1}{s-a_1}+\frac{a_2}{s-a_2}+\ldots+\frac{a_n}{s-a_n}\ge\frac{n}{n-1}.$

Note that the sequences $\{a_i\}\;$ and $\displaystyle\{\frac{a_i}{s-a_i}\}\;$ are similarly ordered, so that, for all $k=2,3,\ldots,n,$

$\displaystyle\begin{align} \frac{a_1}{s-a_1}+\frac{a_2}{s-a_2}&+\ldots+\frac{a_n}{s-a_n}\\ &\ge\frac{a_1}{s-a_k}+\frac{a_2}{s-a_{k+1}}+\ldots+\frac{a_n}{s-a_{k-1}}. \end{align}$

Adding up all $n-1\;$ inequalities gives the desired result.

Note

For $n=3,\;$ the inequality $\displaystyle\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\ge\frac{3}{2}\;$ is known as Nesbitt's inequality.

Example 3

For real numbers $a,b,c,$

$\displaystyle ab+bc+ca\le\frac{(a+b+c)^2}{3}.$

Indeed, the latter inequality is equivalent to $ab+bc+ca\le a^2+b^2+c^2\;$ which is true by rearrangement.

Example 4

This example has been suggested by Leo Giugiuc.

For $n\gt 0\;$ and any sequence of positive real numbers $x_1,x_2,\ldots,x_N,\;$

$\displaystyle\sum_{i=1}^{N}\frac{x_{i}^{n+1}}{x_{\tau(i)}}\ge\sum_{i=1}^{N}x_{i}^{n},$

where $\tau\;$ is an arbitrary permutation of the indices.

Since $\tau\;$ is arbitrary, we can think of $x_i\;$ as a not decreasing sequence: $x_1\le x_2\le\ldots\le x_N.\;$ Then the sequence of the reciprocals $\displaystyle\frac{1}{x_i},\ldots,\frac{1}{x_N}\;$ is not increasing. It follows that, for any rearrangement $\tau,\;$

$\displaystyle\sum_{i=1}^{N}\frac{x_{i}^{n+1}}{x_{\tau(i)}}\ge\sum_{i=1}^{N}\frac{x_{i}^{n+1}}{x_{i}}=\sum_{i=1}^{N}x_{i}^{n}.$

More generally,

for real $m,n,\;n\gt m,\;$ and any sequence of positive real numbers $x_1,x_2,\ldots,x_N,\;$

$\displaystyle\sum_{i=1}^{N}\frac{x_{i}^{n+m}}{x_{\tau(i)}^m}\ge\sum_{i=1}^{N}x_{i}^{n},$

where $\tau\;$ is an arbitrary permutation of the indices.

References

  1. Kin-Yin Li, Rearrangement Inequality, Mathematical Excalibur, Volume 4, Number 3, January, 1999 - March, 1999
  2. Yue Kwok Choy, Rearrangement Inequality
  3. Samin Riasat, Basics of Olympiad Inequalities
  4. IMOMath, Rearrangement Inequality. Chebyshev’s Inequality
  5. G. H. Hardy, J. E. Littlewood, G. Polya, Inequalities, Cambridge University Press (2nd edition)
  6. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998
  7. Xu Jiagu, Lecture Notes on Mathematical Olympiad Courses, v 8, (For senior section, v 2), World Scientific, 2012
  8. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999

 

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71528652