Rearrangement Inequality
by Potla, Oct 9, 2009, 6:55 AM
Though underestimated and not-so-widely-used inequality; Rearrangement inequality is extremely useful in solving several Problems. Several inequalities can also be derived and proved easily from Rearrangement; such as AM-GM; Chebyshev's inequality and so on.....
Theorem
The sum
is maximal if Sequences 
and 
are similarly sorted; and minimal if sequences and are oppositely sorted.
Main Idea
If you see cyclic terms of the form
then we can maximize or minimize it by rearrangement subject to given conditions. So we can write it into 
or of that structure. After forcing that structure, you can easily shift the terms that are in multiplied form and get a new structure; from which you can force identities or easier inequalities.
This idea might not be clear to the readers so I am giving us some examples of Rearrangement inequality.
Also, I will use frequently a notation :
![\[ \begin{bmatrix} a_1 \ \ a_2 \ \ a_3 \\
b_1 \ \ b_2 \ \ b_3 \end{bmatrix} = a_1b_1 + a_2b_2 + a_3b_3\]](//latex.artofproblemsolving.com/8/6/d/86d8c684b29953e1b03dd236ba71769796e3d46d.png)
![\[ \begin{bmatrix} a_1 \ a_2 \ a_3 \\
b_1 \ b_2 \ b_3 \\
c_1 \ c_2 \ c_3 \end{bmatrix} = a_1b_1c_1 + a_2b_2c_2 + a_3b_3c_3\]](//latex.artofproblemsolving.com/d/6/c/d6c18cf0f538dd0746b062103323ff14afc03f4d.png)
and so on.......
Theorems Derived from Rearrangement
We can prove the AM-GM inequality for
numbers using rearrangement inequality. Here I present a short proof (from Problem solving strategies; Arthur Engel):
Let![$ x_i > 0; c = \sqrt [n]{x_1x_2\cdots x_n}$](//latex.artofproblemsolving.com/6/1/2/6129995bc2b0c3264256ef27bcfcf0bfbcba3c31.png)
. Let 
Define also:
We have the direct consequence
Sequences
are oppositely sorted so that we easily have:
![$ \implies c = \sqrt [n]{x_ix_2\cdots x_n}\leq \frac1n(x_1 + x_2 + \cdots x_n)$](//latex.artofproblemsolving.com/b/6/5/b658fe5f9ceff90a9a9997c7b13c90490c616fe5.png)
So we have derived AM-GM inequality. Next we will prove the Chebyshev's inequality:
Theorem 2(Chebyshev)
(a)If sequences
are similarly sorted then
![\[ \sum_{i = 1}^n a_ib_i\geq \frac {1}{n}(a_1 + a_2 + \cdots a_n)(b_1 + b_2 + \cdots b_n)\]](//latex.artofproblemsolving.com/c/0/4/c04971b80e93698e937144a81d513b80aa533869.png)
And, (b)if sequences are oppositely sorted then we have:
![\[ \sum_{i = 1}^n a_ib_i\leq \frac1n(a_1 + a_2 + \cdots a_n)(b_1 + b_2 + \cdots b_n)\]](//latex.artofproblemsolving.com/d/f/7/df7009d75d1f33df1661e05ef936899d5c34254b.png)
Proof
We have;
![\[ a_1b_1 + a_2b_2\cdots + a_nb_n = a_1b_1 + a_2b_2\cdots + a_nb_n \\
a_1b_1 + a_2b_2\cdots + a_nb_n\geq a_1b_2 + a_2b_3 + \cdots + a_nb_1 \\
a_1b_1 + a_2b_2\cdots + a_nb_n\geq a_1b_3 + a_2b_3 + \cdots + a_n b_1 \\
\vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\
a_1b_1 + a_2b_2\cdots + a_nb_n\geq a_1b_n + a_2b_1 + \cdots a_nb_{n - 1} \\
- - - - - - - - - - - - - - - - - - - - - \\
n(a_1b_1 + a_2b_2\cdots + a_nb_n)\geq (a_1 + a_2 + \cdots a_n)(b_1 + b_2 + \cdots b_n) \\
\implies \sum_{i = 1}^n a_ib_i\geq \frac1n(a_1 + a_2 + \cdots a_n)(b_1 + b_2 + \cdots b_n)\]](//latex.artofproblemsolving.com/6/9/6/6967afa79d94dcd354594fa99d6d65136ca928a2.png)
We can prove (b) also accordingly using Rearrangement 
Nessbitt's inequality proved by rearrangement
For
we have 
We have already proved this using an elegant method by Titu's lemma. We can also prove it using AM-GM inequality, and here I show my prof using Rearrangement:
Sequences
and 
are similarly sorted(why?) so from Rearrangement inequality, we have:
![\[ \begin{bmatrix} a \ \ \ b \ \ \ c \\
\frac1{b + c} \ \frac1{c + a} \ \frac1{a + b} \end{bmatrix}\geq \begin{bmatrix} a \ \ \ b \ \ \ c \\
\frac1{c + a} \ \frac1{a + b}\ \frac {1}{b + c} \end{bmatrix} \\
\begin{bmatrix} a \ \ \ b \ \ \ c \\
\frac1{b + c} \ \frac1{c + a} \ \frac1{a + b} \end{bmatrix}\geq \begin{bmatrix} a \ \ \ b \ \ \ c \\
\frac1{a + b} \ \frac1{b + c}\ \frac {1}{a + c} \end{bmatrix} \\
- - - - - - - - - - - - - - - - - - - \\
\implies 2\sum\frac {a}{b + c}\geq \sum \frac {a}{a + c} + \sum \frac c{a + c} = 3\]](//latex.artofproblemsolving.com/5/1/0/510f545323f387621f5d9e1870fcc67127fed101.png)
So we are done.
Another problem
show that 
We have, from easy rearrangement that
![\[ LHS\ge \frac {a^2}{ab} + \frac {b^2}{bc} + \frac {c^2}{ac} = \frac ab + \frac bc + \frac ca \geq 3\]](//latex.artofproblemsolving.com/0/0/5/005f2a815d1b944d70787806673567d79c9f4ed0.png)
where the last one follows from AM-GM.
______________________________________________________
Applications
Prove that 
where
Indeed we have :
![\[ a^3 + b^3 + c^3 = \begin{bmatrix} a \ \ \ b \ \ \ c \\
a^2 \ \ b^2 \ \ c^2 \end{bmatrix}\geq \begin{bmatrix} a \ \ \ b \ \ \ c \\
c^2 \ \ a^2 \ \ b^2 \end{bmatrix} = a^2b + b^2c + c^2a\]](//latex.artofproblemsolving.com/f/d/c/fdce2e94167afdf897e9abfd5c5deb9c57f8b4a4.png)
Q.E.D.
Prove that 
Of course;
![\[ a^4 + b^4 + c^4 = \begin{bmatrix} a^2 \ b^2 \ c^2 \\
a \ b \ c \\
a \ b \ c \end{bmatrix}\geq \begin{bmatrix} a^2 \ b^2 \ c^2 \\
b \ c \ a \\
c \ a \ b \end{bmatrix} = a^2bc + b^2ca + c^2ab\]](//latex.artofproblemsolving.com/7/b/7/7b701ead901665f0d5abd39273c388458db9ad3e.png)
Let a,b and c be positive real numbers. Prove that 
Taking logarithm of both sides to the base
we have:
But, since sequences and 
are similarly sorted; and:
Hence from Rearrangement inequality, we obviously have:
![\[ \begin{bmatrix} \ln a ;\ \ln b; \ \ln c \\
a;\ \ b;\ \ c \end{bmatrix}\geq \begin{bmatrix} \ln a\ ;\ \ \ln b\ ;\ \ \ln c \\
\frac {a + b + c}{3};\ \frac {a + b + c}{3};\ \frac {a + b + c}{3} \end{bmatrix}\]](//latex.artofproblemsolving.com/2/f/9/2f9d8deed442f2830d7fe671d1a45e74c7044de1.png)
Hence the result.
Let Prove that; if 
we always have:
![\[ \frac1{a^2} + \frac1{b^2} + \frac1{c^2}\geq 3 + \frac {2(a^3 + b^3 + c^3)}{abc}\]](//latex.artofproblemsolving.com/3/b/4/3b4292d3463f348945f81b4ed1ad943569696f54.png)
Solution
What happens if we apply Cauchy like
?
Then we must prove that
which is impossible. So direct Cauchy gives us a weak result.
What can we do? Rearrangement or AM-GM to the rescue. We rewrite the inequality as:
![\[ (a^2 + b^2 + c^2)\left(\frac1{a^2} + \frac1{b^2} + \frac1{c^2}\right)\geq 3 + \frac {2(a^3 + b^3 + c^3)}{abc}\]](//latex.artofproblemsolving.com/2/f/8/2f8aa2e35ed4b8ab6d361f5e5863ba823c62aaa2.png)
Now we just expand the LHS; so we are left to prove:
![\[ 3 + \sum_{sym} \frac {a^2}{b^2}\geq 2\sum_{cyc} \frac {a^2}{bc}+3\]](//latex.artofproblemsolving.com/9/c/0/9c031bfd96826856dfcdd4078ad4d842f41469d5.png)
![\[ \implies \sum_{cyc} \left[\frac {a^2}{b^2} + \frac {a^2}{c^2}\right]\geq \sum_{cyc}\left(2\frac {a^2}{bc}\right)\]](//latex.artofproblemsolving.com/a/8/3/a834803e9172940694ea00805dab85db5d8dd2d4.png)
Which is perfectly true from Rearrangement or AM-GM inequality.
(AM-GM is applied directly here. Can you find a proof by direct rearrangement?
)
For show that
![\[ \sum_{cyc}\frac {a^2 + bc}{b + c}\geq a + b + c\]](//latex.artofproblemsolving.com/4/9/6/496894495902a08b57a6887969e9f2cfa866534d.png)
Solution
This is a really old and well - known problem. My proof of this shows the full power of rearrangement.
There are several ways of proving this, but this is a new solution that I found, which, in my opinion, is the simplest and most elementary solution.
We rewrite the inequality as
Observe that sequences
and 
are similarly sorted.
Hence from rearrangement;
So plugging this inequality into our required problem, we have
![\[ LHS \geq \sum \frac {b^2 + bc}{b + c} = \sum \frac {b(b + c)}{b + c} = a + b + c\]](//latex.artofproblemsolving.com/6/f/a/6fad56b5e518b3e4cb22bc8bb1dedb73b3dfdfc4.png)
I finish my proof here 
.
(To be Updated)
For more problems, see my next entry on Chebyshev's inequality
Theorem
The sum
is maximal if Sequences 
and 
are similarly sorted; and minimal if sequences and are oppositely sorted.Main Idea
If you see cyclic terms of the form
then we can maximize or minimize it by rearrangement subject to given conditions. So we can write it into 
or of that structure. After forcing that structure, you can easily shift the terms that are in multiplied form and get a new structure; from which you can force identities or easier inequalities.This idea might not be clear to the readers so I am giving us some examples of Rearrangement inequality.
Also, I will use frequently a notation :
![\[ \begin{bmatrix} a_1 \ \ a_2 \ \ a_3 \\
b_1 \ \ b_2 \ \ b_3 \end{bmatrix} = a_1b_1 + a_2b_2 + a_3b_3\]](http://latex.artofproblemsolving.com/8/6/d/86d8c684b29953e1b03dd236ba71769796e3d46d.png)
![\[ \begin{bmatrix} a_1 \ a_2 \ a_3 \\
b_1 \ b_2 \ b_3 \\
c_1 \ c_2 \ c_3 \end{bmatrix} = a_1b_1c_1 + a_2b_2c_2 + a_3b_3c_3\]](http://latex.artofproblemsolving.com/d/6/c/d6c18cf0f538dd0746b062103323ff14afc03f4d.png)
and so on.......Theorems Derived from Rearrangement
We can prove the AM-GM inequality for
numbers using rearrangement inequality. Here I present a short proof (from Problem solving strategies; Arthur Engel):Let
![$ x_i > 0; c = \sqrt [n]{x_1x_2\cdots x_n}$](http://latex.artofproblemsolving.com/6/1/2/6129995bc2b0c3264256ef27bcfcf0bfbcba3c31.png)
. Let 
Define also:
We have the direct consequence
Sequences
are oppositely sorted so that we easily have:
![$ \implies c = \sqrt [n]{x_ix_2\cdots x_n}\leq \frac1n(x_1 + x_2 + \cdots x_n)$](http://latex.artofproblemsolving.com/b/6/5/b658fe5f9ceff90a9a9997c7b13c90490c616fe5.png)
So we have derived AM-GM inequality. Next we will prove the Chebyshev's inequality:
Theorem 2(Chebyshev)
(a)If sequences
are similarly sorted then![\[ \sum_{i = 1}^n a_ib_i\geq \frac {1}{n}(a_1 + a_2 + \cdots a_n)(b_1 + b_2 + \cdots b_n)\]](http://latex.artofproblemsolving.com/c/0/4/c04971b80e93698e937144a81d513b80aa533869.png)
And, (b)if sequences are oppositely sorted then we have:![\[ \sum_{i = 1}^n a_ib_i\leq \frac1n(a_1 + a_2 + \cdots a_n)(b_1 + b_2 + \cdots b_n)\]](http://latex.artofproblemsolving.com/d/f/7/df7009d75d1f33df1661e05ef936899d5c34254b.png)
ProofWe have;
![\[ a_1b_1 + a_2b_2\cdots + a_nb_n = a_1b_1 + a_2b_2\cdots + a_nb_n \\
a_1b_1 + a_2b_2\cdots + a_nb_n\geq a_1b_2 + a_2b_3 + \cdots + a_nb_1 \\
a_1b_1 + a_2b_2\cdots + a_nb_n\geq a_1b_3 + a_2b_3 + \cdots + a_n b_1 \\
\vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\
a_1b_1 + a_2b_2\cdots + a_nb_n\geq a_1b_n + a_2b_1 + \cdots a_nb_{n - 1} \\
- - - - - - - - - - - - - - - - - - - - - \\
n(a_1b_1 + a_2b_2\cdots + a_nb_n)\geq (a_1 + a_2 + \cdots a_n)(b_1 + b_2 + \cdots b_n) \\
\implies \sum_{i = 1}^n a_ib_i\geq \frac1n(a_1 + a_2 + \cdots a_n)(b_1 + b_2 + \cdots b_n)\]](http://latex.artofproblemsolving.com/6/9/6/6967afa79d94dcd354594fa99d6d65136ca928a2.png)
We can prove (b) also accordingly using Rearrangement Nessbitt's inequality proved by rearrangement
For
we have 
We have already proved this using an elegant method by Titu's lemma. We can also prove it using AM-GM inequality, and here I show my prof using Rearrangement:
Sequences
and 
are similarly sorted(why?) so from Rearrangement inequality, we have:![\[ \begin{bmatrix} a \ \ \ b \ \ \ c \\
\frac1{b + c} \ \frac1{c + a} \ \frac1{a + b} \end{bmatrix}\geq \begin{bmatrix} a \ \ \ b \ \ \ c \\
\frac1{c + a} \ \frac1{a + b}\ \frac {1}{b + c} \end{bmatrix} \\
\begin{bmatrix} a \ \ \ b \ \ \ c \\
\frac1{b + c} \ \frac1{c + a} \ \frac1{a + b} \end{bmatrix}\geq \begin{bmatrix} a \ \ \ b \ \ \ c \\
\frac1{a + b} \ \frac1{b + c}\ \frac {1}{a + c} \end{bmatrix} \\
- - - - - - - - - - - - - - - - - - - \\
\implies 2\sum\frac {a}{b + c}\geq \sum \frac {a}{a + c} + \sum \frac c{a + c} = 3\]](http://latex.artofproblemsolving.com/5/1/0/510f545323f387621f5d9e1870fcc67127fed101.png)
So we are done.Another problem
show that 
We have, from easy rearrangement that
![\[ LHS\ge \frac {a^2}{ab} + \frac {b^2}{bc} + \frac {c^2}{ac} = \frac ab + \frac bc + \frac ca \geq 3\]](http://latex.artofproblemsolving.com/0/0/5/005f2a815d1b944d70787806673567d79c9f4ed0.png)
where the last one follows from AM-GM.______________________________________________________
Applications
Prove that 
where Indeed we have :
![\[ a^3 + b^3 + c^3 = \begin{bmatrix} a \ \ \ b \ \ \ c \\
a^2 \ \ b^2 \ \ c^2 \end{bmatrix}\geq \begin{bmatrix} a \ \ \ b \ \ \ c \\
c^2 \ \ a^2 \ \ b^2 \end{bmatrix} = a^2b + b^2c + c^2a\]](http://latex.artofproblemsolving.com/f/d/c/fdce2e94167afdf897e9abfd5c5deb9c57f8b4a4.png)
Q.E.D.
Prove that 
Of course;
![\[ a^4 + b^4 + c^4 = \begin{bmatrix} a^2 \ b^2 \ c^2 \\
a \ b \ c \\
a \ b \ c \end{bmatrix}\geq \begin{bmatrix} a^2 \ b^2 \ c^2 \\
b \ c \ a \\
c \ a \ b \end{bmatrix} = a^2bc + b^2ca + c^2ab\]](http://latex.artofproblemsolving.com/7/b/7/7b701ead901665f0d5abd39273c388458db9ad3e.png)
lies between minimum and maximum of 
the we also have:![\[ \begin{bmatrix} a_1 \ \ a_2 \ \cdots \cdots \ a_n \\
b_1 \ \ b_2 \ \ \cdots \cdots \ b_n \end{bmatrix}\geq \begin{bmatrix} a_1 \ \ a_2 \ \ \cdots \cdots \ a_n \\
c \ \ \ c \ \ \ \cdots \cdots \ \ c \end{bmatrix}\]](http://latex.artofproblemsolving.com/6/1/7/617029c845d22b9f41b45b56362897e7854f1ee4.png)
Let a,b and c be positive real numbers. Prove that 
Taking logarithm of both sides to the base
we have:
But, since sequences
and 
are similarly sorted; and:
Hence from Rearrangement inequality, we obviously have:
![\[ \begin{bmatrix} \ln a ;\ \ln b; \ \ln c \\
a;\ \ b;\ \ c \end{bmatrix}\geq \begin{bmatrix} \ln a\ ;\ \ \ln b\ ;\ \ \ln c \\
\frac {a + b + c}{3};\ \frac {a + b + c}{3};\ \frac {a + b + c}{3} \end{bmatrix}\]](http://latex.artofproblemsolving.com/2/f/9/2f9d8deed442f2830d7fe671d1a45e74c7044de1.png)
Hence the result. 
Let Prove that; if 
we always have:![\[ \frac1{a^2} + \frac1{b^2} + \frac1{c^2}\geq 3 + \frac {2(a^3 + b^3 + c^3)}{abc}\]](http://latex.artofproblemsolving.com/3/b/4/3b4292d3463f348945f81b4ed1ad943569696f54.png)
Solution
What happens if we apply Cauchy like
?Then we must prove that
which is impossible. So direct Cauchy gives us a weak result.What can we do? Rearrangement or AM-GM to the rescue. We rewrite the inequality as:
![\[ (a^2 + b^2 + c^2)\left(\frac1{a^2} + \frac1{b^2} + \frac1{c^2}\right)\geq 3 + \frac {2(a^3 + b^3 + c^3)}{abc}\]](http://latex.artofproblemsolving.com/2/f/8/2f8aa2e35ed4b8ab6d361f5e5863ba823c62aaa2.png)
Now we just expand the LHS; so we are left to prove:![\[ 3 + \sum_{sym} \frac {a^2}{b^2}\geq 2\sum_{cyc} \frac {a^2}{bc}+3\]](http://latex.artofproblemsolving.com/9/c/0/9c031bfd96826856dfcdd4078ad4d842f41469d5.png)
![\[ \implies \sum_{cyc} \left[\frac {a^2}{b^2} + \frac {a^2}{c^2}\right]\geq \sum_{cyc}\left(2\frac {a^2}{bc}\right)\]](http://latex.artofproblemsolving.com/a/8/3/a834803e9172940694ea00805dab85db5d8dd2d4.png)
Which is perfectly true from Rearrangement or AM-GM inequality.(AM-GM is applied directly here. Can you find a proof by direct rearrangement?
)
For show that![\[ \sum_{cyc}\frac {a^2 + bc}{b + c}\geq a + b + c\]](http://latex.artofproblemsolving.com/4/9/6/496894495902a08b57a6887969e9f2cfa866534d.png)
Solution
This is a really old and well - known problem. My proof of this shows the full power of rearrangement.
There are several ways of proving this, but this is a new solution that I found, which, in my opinion, is the simplest and most elementary solution.
We rewrite the inequality as
Observe that sequences
and 
are similarly sorted.Hence from rearrangement;
So plugging this inequality into our required problem, we have
![\[ LHS \geq \sum \frac {b^2 + bc}{b + c} = \sum \frac {b(b + c)}{b + c} = a + b + c\]](http://latex.artofproblemsolving.com/6/f/a/6fad56b5e518b3e4cb22bc8bb1dedb73b3dfdfc4.png)
I finish my proof here 
.(To be Updated)
For more problems, see my next entry on Chebyshev's inequality
This post has been edited 1 time. Last edited by Potla, Jan 20, 2011, 8:01 AM
March 2012
December 2011