Rearrangement Inequality

Original Post.

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

S_n = \sum_{i = 1}^n a_ib_i

is maximal if Sequences \{a_i\} and \{b_i\} are similarly sorted; and minimal if sequences \{a_i\} and \{b_i\} are oppositely sorted.
Main Idea
If you see cyclic terms of the form \sum a_ib_i then we can maximize or minimize it by rearrangement subject to given conditions. So we can write it into S\geq \sum_{cyc}a_ib_{n - i} 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

\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
and so on…
Theorems Derived from Rearrangement
We can prove the AM-GM inequality for n 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}. Let a_j = \frac {\prod_{i = 1}^j x_i}{c^i}
Define also: b_i = \frac {1}{a_i}
We have the direct consequence a_n = b_n = 1
Sequences \{a_i\}; \{b_i\} are oppositely sorted so that we easily have:
\sum_{i = 1}^n a_ib_i\leq a_1b_n + a_2b_1 + \cdots a_nb_{n - 1}
\implies\underbrace{ 1 + 1 + \cdots1}\le \sum_{i = 1}^n \frac {x_i}{c}
\implies c = \sqrt [n]{x_ix_2\cdots x_n}\leq \frac1n(x_1 + x_2 + \cdots x_n)
So we have derived AM-GM inequality. Next we will prove the Chebyshev’s inequality:
Theorem 2(Chebyshev)
(a)If sequences a_i; b_i 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)
And, (b)if sequences a_i; b_i 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)
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...
We can prove (b) also accordingly using Rearrangement :)
Nessbitt’s inequality proved by rearrangement
For a,b,c > 0 we have \frac a{b + c} + \frac b{c + a} + \frac c{a + b}\geq \frac32
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 a,b,c and \frac1{b + c}; \frac {1}{c + a}; \frac1{a + b} 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...
So we are done.
Another problem
a,b,c > 0; show that \frac {a^2}{bc} + \frac {b^2}{ca} + \frac {c^2}{ab}\ge 3
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
where the last one follows from AM-GM.
______________________________________________________
Applications
\boxed{1} Prove that a^3 + b^3 + c^3\geq a^2b + b^2c + c^2a where a,b,c > 0
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...
Q.E.D.
\boxed{2} Prove that a^4 + b^4 + c^4\geq a^2bc + b^2ca + c^2ab\forall a,b,c\geq 0
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 \...
Another argument

Note: So, as we see, rearrangement can also be applied in logarithmic inequalities, as in example 3 below ; and we can also apply it using the argument that: If a number c lies between minimum and maximum of b_1,b_2,\cdots b_n 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...

\boxed{3} Let a,b and c be positive real numbers. Prove that {a}^a{b}^b{c}^c\geq(abc)^{\frac {a + b + c}{3}}
Taking logarithm of both sides to the base e we have:
a\ln a + b\ln b + c\ln c\geq \left(\frac {a + b + c}{3}\right)(\ln a + \ln b + \ln c)
But, since sequences a,b,c and \ln a, \ln b, \ln c are similarly sorted; and:
\min\{a,b,c\}\leq \frac {a + b + c}{3}\leq \max\{a,b,c\}
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 \\\fr...
Hence the result. :)
\boxed{5} Let a,b,c > 0 Prove that; if a^2 + b^2 + c^2 = 1 we always have:
\frac1{a^2} + \frac1{b^2} + \frac1{c^2}\geq 3 + \frac {2(a^3 + b^3 + c^3)}{abc}

Solution
What happens if we apply Cauchy like (a^2 + b^2 + c^2)\left(\frac1{a^2} + \frac1{b^2} + \frac1{c^2}\right)\geq 9?
Then we must prove that 3abc\geq a^3 + b^3 + c^3 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}
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

\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)
Which is perfectly true from Rearrangement or AM-GM inequality.
(AM-GM is applied directly here. Can you find a proof by direct rearrangement? :P )

\boxed{6}For a,b,c > 0 show that
\sum_{cyc}\frac {a^2 + bc}{b + c}\geq a + b + c

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 \sum \frac {a^2}{b + c} + \sum\frac {bc}{b + c}\geq a + b + c
Observe that sequences \{a^2,b^2, c^2\} and \left\{\frac 1{b + c}; \frac 1{c + a}; \frac 1{a + b}\right\} are similarly sorted.
Hence from rearrangement; \sum \frac {a^2}{b + c}\geq \sum \frac {b^2}{b + c}
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
I finish my proof here ;) \Box.

(To be Updated)
For more problems, see my next entry on Chebyshev’s inequality

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s