# 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

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

- An Inequality for Grade 8
- An Extension of the AM-GM Inequality
- Schur's Inequality
- Newton's and Maclaurin's Inequalities
- Rearrangement Inequality
- Chebyshev Inequality
- Jensen's Inequality
- Muirhead's Inequality
- Bergström's inequality
- Radon's Inequality and Applications
- Jordan and Kober Inequalities, PWW
- A Mathematical Rabbit out of an Algebraic Hat
- An Inequality With an Infinite Series
- An Inequality: 1/2 * 3/4 * 5/6 * ... * 99/100 less than 1/10
- A Low Bound for 1/2 * 3/4 * 5/6 * ... * (2n-1)/2n
- An Inequality: Easier to prove a subtler inequality
- Inequality with Logarithms
- An inequality: 1 + 1/4 + 1/9 + ... less than 2
- Inequality with Harmonic Differences
- An Inequality by Uncommon Induction
- Hlawka's Inequality
- An Inequality in Determinants
- Application of Cauchy-Schwarz Inequality
- An Inequality from Tibet
- An Inequality with Constraint
- An Inequality from Morocco
- An Inequality for Mixed Means
- An Inequality in Integers
- An Inequality in Integers II
- An Inequality in Integers III
- An Inequality with Exponents
- Exponential Inequalities for Means
- A Simple Inequality in Three Variables
- An Asymmetric Inequality
- Linear Algebra Tools for Proving Inequalities
- An Inequality with a Generic Proof
- A Generalization of an Inequality from a Romanian Olympiad
- Area Inequality in Trapezoid
- Improving an Inequality
- RomanoNorwegian Inequality
- Inequality with Nested Radicals II
- Inequality with Powers And Radicals
- Inequality with Two Minima
- Simple Inequality with Many Faces And Variables
- An Inequality with Determinants
- An Inequality with Determinants II
- An Inequality with Determinants III
- An Inequality with Determinants IV
- An Inequality with Determinants V
- An Inequality with Determinants VI
- An Inequality with Determinants VII
- An Inequality in Reciprocals
- An Inequality in Reciprocals II
- An Inequality in Reciprocals III
- Monthly Problem 11199
- A Problem from the Danubius Contest 2016
- A Problem from the Danubius-XI Contest
- An Inequality with Integrals and Rearrangement
- An Inequality with Cot, Cos, and Sin
- A Trigonometric Inequality from the RMM
- An Inequality with Finite Sums
- Hung Viet's Inequality
- Hung Viet's Inequality II
- Hung Viet's Inequality III
- Inequality by Calculus
- Dorin Marghidanu's Calculus Lemma
- An Area Inequality
- A 4-variable Inequality from the RMM
- An Inequality from RMM with Powers of 2
- A Cycling Inequality with Integrals
- A Cycling Inequality with Integrals II
- An Inequality with Absolute Values
- An Inequality from RMM with a Generic 5
- An Elementary Inequality by Non-elementary Means
- Inequality in Quadrilateral
- Marian Dinca's Refinement of Nesbitt's Inequality
- An Inequality in Cyclic Quadrilateral
- An Inequality in Cyclic Quadrilateral II
- An Inequality in Cyclic Quadrilateral III
- An Inequality in Cyclic Quadrilateral IV
- Inequality with Three Linear Constraints
- Inequality with Three Numbers, Not All Zero
- An Easy Inequality with Three Integrals
- Divide And Conquer in Cyclic Sums
- Wu's Inequality
- A Cyclic Inequality in Three Variables
- Dorin Marghidanu's Inequality in Complex Plane
- Dorin Marghidanu's Inequality in Integer Variables
- Dorin Marghidanu's Inequality in Many Variables
- Dorin Marghidanu's Inequality in Many Variables Plus Two More
- Dorin Marghidanu's Inequality with Radicals
- Dorin Marghidanu's Light Elegance in Four Variables
- Dorin Marghidanu's Spanish Problem
- Two-Sided Inequality - One Provenance
- An Inequality with Factorial
- Wonderful Inequality on Unit Circle
- Quadratic Function for Solving Inequalities
- An Inequality Where One Term Is More Equal Than Others
- An Inequality and Its Modifications
- Complicated Constraint - Simple Inequality
- Distance Inequality
- Two Products: Constraint and Inequality
- The power of substitution II: proving an inequality with three variables
- Algebraic-Geometric Inequality
- One Inequality - Two Domains
- Radicals, Radicals, And More Radicals in an Inequality
- An Inequality in Triangle and In General
- Cyclic Inequality with Square Roots
- Dan Sitaru's Cyclic Inequality In Many Variables
- An Inequality on Circumscribed Quadrilateral
- An Inequality with Fractions
- An Inequality with Complex Numbers of Unit Length
- An Inequality with Complex Numbers of Unit Length II
- Le Khanh Sy's Problem
- An Inequality Not in Triangle
- An Acyclic Inequality in Three Variables
- An Inequality with Areas, Norms, and Complex Numbers
- Darij Grinberg's Inequality In Three Variables
- Small Change Makes Big Difference
- Inequality with Two Variables? Think Again
- A Problem From a Mongolian Olympiad for Grade 11
- Sitaru--Schweitzer Inequality
- An Inequality with Cyclic Sums And Products
- Problem 1 From the 2016 Pan-African Math Olympiad
- An Inequality with Integrals and Radicals
- Twin Inequalities in Four Variables: Twin 1
- Twin Inequalities in Four Variables: Twin 2
- Simple Inequality with a Variety of Solutions
- A Partly Cyclic Inequality in Four Variables
- Dan Sitaru's Inequality by Induction
- An Inequality in Three (Or Is It Two) Variables
- An Inequality in Four Weighted Variables
- An Inequality in Fractions with Absolute Values
- Inequalities with Double And Triple Integrals
- An Old Inequality
- Dan Sitaru's Amazing, Never Ending Inequality
- Leo Giugiuc's Exercise
- Another Inequality with Logarithms, But Not Really
- A Cyclic Inequality of Degree Four
- An Inequality Solved by Changing Appearances
- Distances to Three Points on a Circle
- An Inequality with Powers And Logarithm
- Four Integrals in One Inequality
- Same Integral, Three Intervals
- Dorin Marghidanu's Inequality with Generalization
- Dan Sitaru's Inequality with Three Related Integrals and Derivatives
- An Inequality in Two Or More Variables
- An Inequality in Two Or More Variables II
- A Not Quite Cyclic Inequality
- Dan Sitaru's Inequality: From Three Variables to Many in Two Ways
- An Inequality with Sines But Not in a Triangle
- An Inequality with Angles and Integers
- Sladjan Stankovik's Inequality In Four Variables
- An Inequality with Two Pairs of Triplets
- A Refinement of Turkevich's Inequality
- Dan Sitaru's Exercise with Pi and Ln
- Problem 4165 from Crux Mathematicorum
- Leo Giugiuc's Cyclic Quickie in Four Variables
- Dan Sitaru's Cyclic Inequality in Four Variables
- A Not Quite Cyclic Inequality from Tibet
- Three Variables, Three Constraints, Two Inequalities (Only One to Prove) - by Leo Giugiuc
- An inequality in 2+2 variables from SSMA magazine
- Kunihiko Chikaya's Inequality with Parameter
- Dorin Marghidanu's Permuted Inequality

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

Copyright © 1996-2017 Alexander Bogomolny62685722 |