Rearrangement Inequality. Chebyshev’s Inequality
Theorem 1 (Rearrangement inequality)
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_1 \), \( \sigma_2 \), \( \dots \), \( \sigma_n \) is any permutation of \( \{1,2,\dots, n\} \), then the following inequality holds:
\[ x_1y_n+x_2y_{n-1}+\cdots+x_ny_1\leq x_1y_{\sigma_1}+x_2y_{\sigma_2}+\cdots+ x_ny_{\sigma_n}\leq x_1y_1+x_2y_2+\cdots+x_ny_n.\]
Let us prove the right inequality. The left one will follow by applying the right one to the sequences \( x_1 \), \( x_2 \), \( \dots \), \( x_n \) and \( -y_n \), \( -y_{n-1} \), \( \dots \), \( -y_1 \).
We will prove the right inequality by induction on \( n \). For \( n=2 \), the statement can be easily proved. Assume that the statement holds for all pairs of sequences of lengths \( 1 \), \( 2 \), \( \dots \), \( n \). Let \( x_1\leq \) \( x_2\leq \) \( \cdots\leq \) \( x_{n+1} \) and \( y_1\leq \) \( y_2\leq \) \( \cdots\leq \) \( y_{n+1} \) be two sequences of real numbers, and let \( \sigma_1 \), \( \sigma_2 \), \( \dots \), \( \sigma_{n+1} \) be a permutation of \( \{1,2,\dots, n+1\} \). Let \( i \) be the integer such that \( \sigma_i=n+1 \).
Then we have \[ x_1y_{\sigma_1}+x_2y_{\sigma_2}+\cdots+\left(x_iy_{\sigma_i}+x_{i+1}y_{\sigma_{i+1}}\right)+\cdots+x_{n+1}y_{n+1}
\leq x_1y_{\sigma_1}+x_2y_{\sigma_2}+\cdots+ \left(x_iy_{\sigma_{i+1}}+x_{i+1}y_{\sigma_{i}}\right)+\cdots+x_{n+1}y_{n+1}.\]
The last inequality holds because we applied the case \( n=2 \) for the non-decreasing sequences \( (x_i, x_{i+1}) \) and \( \left(y_{\sigma_{i+1}},y_{\sigma_{i}}\right) \). The previous inequality can be now written as
\[ \sum_{j=1}^{n+1}x_jy_{\sigma_j}\leq\sum_{j=1}^{n+1} x_jy_{\tau^1_j},\] where \( \tau^1_1 \), \( \tau^1_2 \), \( \dots \), \( \tau^1_{n+1} \) is the permutation obtained from \( \sigma_1 \), \( \sigma_2 \), \( \dots \), \( \sigma_{n+1} \) by transposing the term \( n+1 \) with the one that is adjacent and to the right. Repeating this procedure we obtain the inequality \[ \sum_{i=j}^{n+1}x_jy_{\sigma_j}\leq \sum_{j=1}^{n+1}x_jy_{\tau^{n+1-i}_j}.\]
We now have \( \tau^{n+1-i}_{n+1}=n+1 \) and we can apply inductional hypothesis to obtain
\[ \sum_{j=1}^{n}x_jy_{\tau^{n+1-i}_j}\leq\sum_{j=1}^n x_jy_j\quad\Rightarrow\quad \sum_{j=1}^{n+1}x_jy_{\tau^{n+1-i}_j}\leq \sum_{n=1}^{n+1}x_jy_j.\]
Let us show by example how we can prove the inequality between arithmetic and geometric mean using the rearrangement inequality. We will prove it for \( n=4 \), and from there it will be clear how one can generalize the method.
Problem 1
If \( a \), \( b \), \( c \), and \( d \) are positive real numbers prove that \[ a^4+b^4+c^4+d^4\geq 4abcd.\]
Assume that \( a\leq b\leq c\leq d \). Applying the rearrangement to the sequences \( (c,d) \) and \( (c^3,d^3) \) we obtain \[ dc^3+cd^3\leq c^4+d^4.\] Applying the same inequality to the sequences \( (b,d) \) and \( (b^3,cd^2) \) we obtain \( db^3+bcd^2\leq b^4+cd^3 \). Together with the previous inequality we have \[ db^3+dc^3+bcd^2\leq b^4+c^4+d^4.\] We now apply the rearrangement inequality to the sequences \( (a,d) \) and \( (a^3,bcd) \) to obtain \( da^3+abcd\leq a^4+bcd^2 \) which together with the previous inequality implies \[ da^3+db^3+dc^3+abcd\leq a^4+b^4+c^4+d^4.\] It suffices to prove that \( 3abcd\leq da^3+db^3+dc^4 \) which is equivalent to \( 3abc\leq a^3+b^3+c^3 \). For this we use the same argument as before.
Theorem 2 (Chebyshev)
Let \( a_1\geq a_2\geq\cdots\geq a_n \) and
\( b_1\geq b_2\geq\cdots\geq
b_n \) be real numbers. Then
\begin{eqnarray*}
n\sum_{i=1}^n
a_ib_i\geq\left(\sum_{i=1}^n a_i \right)\left(\sum_{i=1}^n
b_i\right)\geq n\sum_{i=1}^n a_ib_{n+1-i}.\quad\quad\quad\quad\quad (1)
\end{eqnarray*} The two inequalities
become equalities at the same time when \( a_1=a_2=\cdots=a_n \) or
\( b_1=b_2=\cdots=b_n \).
According to rearrangement inequality we have the following relations:
\begin{eqnarray*}
a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n&\geq&a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n \geq a_1b_n+a_2b_{n-1}+\cdots +a_nb_1 \\
a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n&\geq&a_1b_2+a_2b_3+a_3b_4+\cdots+a_nb_1\geq a_1b_n+a_2b_{n-1}+\cdots +a_nb_1\\
a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n&\geq&a_1b_3+a_2b_4+a_3b_5+\cdots+a_nb_2\geq a_1b_n+a_2b_{n-1}+\cdots +a_nb_1\\
&&\vdots\\
a_1b_1+a_2b_2+a_3b_3+\cdots+a_nb_n&\geq&a_1b_n+a_2b_1+a_3b_2+\cdots+a_nb_{n-1}\geq a_1b_n+a_2b_{n-1}+\cdots +a_nb_1.
\end{eqnarray*}
Summing up these \( n \) inequalities we obtain (1).
We will prove the following generalization of the above theorem. The left inequality of Theorem 2 follows by substituting \( m_i=\frac1n \) in Theorem 3, and the right inequality follows from the application of the left inequality to the sequences \( (a_i) \) and \( (c_i) \) with \( c_i=-b_{n+1-i} \).
Theorem 3 (Generalized Chebyshev’s Inequality)
Let \( a_1\geq a_2\geq\cdots\geq a_n \) and
\( b_1\geq b_2\geq\cdots\geq
b_n \) be any real numbers, and
\( m_1,\dots, m_n \) non-negative
real numbers whose sum is \( 1 \). Then
\begin{eqnarray*}
\sum_{i=1}^n
a_ib_im_i\geq\left(\sum_{i=1}^n a_i m_i\right)
\left(\sum_{i=1}^n
b_im_i\right).\quad\quad\quad\quad\quad (2)
\end{eqnarray*} The inequality
become an equality if and only if \( a_1=a_2=\cdots=a_n \) or
\( b_1=b_2=\cdots=b_n \).
From \( (a_i-a_j)(b_i-b_j)\geq 0 \) we get:
\begin{eqnarray*}
\sum_{i,j}(a_i-a_j)(b_i-b_j)m_im_j\geq 0.\quad\quad\quad\quad\quad(3)\end{eqnarray*}
Since \( \left(\sum_{i=1}^n a_im_i\right)\cdot
\left(\sum_{i=1}^n b_im_i\right)=\sum_{i,j}
a_ib_jm_im_j \), (3) implies
that \begin{eqnarray*}0&\leq&
\sum_{i,j}a_ib_im_im_j-\sum_{i,j}
a_ib_jm_im_j-\sum_{i,j}a_jb_im_jm_i + \sum_{i,j}a_jb_j
m_im_j\\
&=& 2\left[\sum_i a_ib_im_i-
\left(\sum_i a_im_i\right)\left(\sum_i b_im_i\right)
\right].\;
\end{eqnarray*}
Problem 1
If \( a \), \( b \), and \( c \) are positive real numbers, prove the inequality
\[ \frac{ab}{a+b}+\frac{bc}{b+c}+\frac{ca}{c+a}\leq\frac{3(ab+bc+ca)}{2(a+b+c)}.\]
Assume that \( a\leq b\leq c \). Then we have \( a+b\geq a+c\geq c+a \). We also have \( \frac1a\leq \frac1b\leq \frac1c \) implying \( \frac1a+\frac1b\leq\frac1a+\frac1c\leq\frac1b+\frac1c \) and \[ \frac1{\frac1a+\frac1b}\geq \frac1{\frac1a+\frac1c}\geq \frac1{\frac1b+\frac1c}.\] The last three inequalities can be rewritten as \[ \frac{ab}{a+b}\geq\frac{ac}{a+c}\geq\frac{bc}{b+c}.\]
Chebyshev’s inequality now implies \[ 3\cdot \left((a+b)\cdot \frac{ab}{a+b}+(a+c)\cdot \frac{ac}{a+c}+(b+c)\frac{bc}{b+c}\right)\geq \left((a+b)+(a+c)+(b+c)\right)\cdot \left(\frac{ab}{a+b}+\frac{ac}{a+c}+\frac{bc}{b+c}\right).\]
The last inequality is equivalent to the required one. The eqeuality holds if and only if \( a=b=c \).
Problem 3
Prove that the sum of distances of
the orthocenter from the
sides of an acute triangle is less than or
equal to \( 3r \), where the \( r \) is
the inradius.
Denote \( a=BC \), \( b=CA \), \( c=AB \) and
let \( S_{ABC} \) denote the area of the triangle \( ABC \).
Let \( d_A \), \( d_B \), \( d_C \) be the distances from
\( H \) to \( BC \), \( CA \), \( AB \), and \( A^{\prime} \), \( B^{\prime} \), \( C^{\prime} \)
the feet of perpendiculars from \( A \), \( B \), \( C \). Then
we have
\( ad_a+bd_b+cd_c=2(S_{BCH}+S_{ACH}+S_{ABH})=2P \).
On the other hand if we assume that \( a\geq
b\geq c \), it is easy to prove that
\( d_A\geq d_B\geq
d_C \). Indeed, \( a\geq b \) implies \( \angle A\geq \angle B \)
hence \( \angle HCB^{\prime} \leq \angle HCA^{\prime} \) and
\( HB^{\prime}\leq HA^{\prime} \).
The Chebyshev’s inequality implies
\[
(a+b+c)r=2P=ad_a+bd_b+cd_c\geq\frac13(a+b+c)(d_a+d_b+d_c).
\]
Problem 4
If \( a, b \), and \( c \) are the
lengths of the sides of a triangle, \( s \) its
semiperimeter, and
\( n\geq 1 \) an integer, prove that
\[ \frac{a^n}{b+c}+\frac{b^n}{c+a}+ \frac{c^n}{a+b} \geq
\left(\frac23\right)^{n-2} \cdot s^{n-1}.\]
Applying the Chebyshev’s inequality
first we get \[ \frac{a^n}{b+c}+\frac{b^n}{c+a}+ \frac{c^n}{a+b}
\geq \frac{a^n+b^n+c^n}3\cdot \left(\frac1{a+b}+\frac1{b+c} +
\frac1{c+a}\right).\] The Cauchy-Schwartz inequality
gives: \[ 2(a+b+c)\left(\frac1{a+b} + \frac1{b+c}+\frac1{c+a}\right)
\geq 9,\]
and the inequality \( M_n\geq M_2 \) gives
\[ \frac{a^n+b^n+c^n}3 \geq
\left(\frac{a+b+c}3\right)^n.\]
In summary \begin{eqnarray*}
\frac{a^n}{b+c}+\frac{b^n}{c+a}+ \frac{c^n}{a+b}&\geq &
\left(\frac{a+b+c}3\right)^n\left(\frac1{a+b} + \frac1{b+c} +
\frac1{c+a}\right)\\ & \geq &
\frac13\cdot\frac12\cdot
\left(\frac23s\right)^{n-1}\cdot 9 =
\left(\frac23\right)^{n-2}s^{n-1}. \end{eqnarray*}
Problem 5
Let \( 0< x_1
\leq x_2 \leq \cdots \leq x_n \) (\( n\geq 2 \)) and \[ \frac1{1+x_1} +
\frac1{1+x_2}+ \cdots + \frac1{1+x_n} = 1.\] Prove that
\[ \sqrt{x_1} + \sqrt{x_2} + \cdots + \sqrt{x_n} \geq (n-1) \left(
\frac1{\sqrt{x_1}}+ \frac1{\sqrt{x_2}} + \cdots +
\frac1{\sqrt{x_n}}\right).\]
It is enough to prove that
\begin{eqnarray}\nonumber &&
\left(\sqrt{x_1}+\frac1{\sqrt{x_1}}\right) +
\left(\sqrt{x_2}+\frac1{\sqrt{x_2}}\right)+ \cdots +
\left(\sqrt{x_n}+\frac1{\sqrt{x_n}}\right)\\
\nonumber & \geq &
n\left(
\frac1{\sqrt{x_1}}+ \frac1{\sqrt{x_2}} + \cdots +
\frac1{\sqrt{x_n}}\right),\end{eqnarray} or equivalently
\begin{eqnarray}\nonumber &&
\left(\frac{1+x_1}{\sqrt{x_1}} + \cdots +
\frac{1+x_n}{\sqrt{x_n}}\right) \left(\frac1{1+x_1} +
\frac1{1+x_2}+ \cdots + \frac1{1+x_n}\right)\\ \nonumber
& \geq &n\cdot
\left(\frac1{\sqrt{x_1}}+ \frac1{\sqrt{x_2}} + \cdots +
\frac1{\sqrt{x_n}}\right).\end{eqnarray}
Consider the function \( f(x)=\sqrt x +
\frac{1}{\sqrt{x}} = \frac{x+1}{\sqrt x},
x\in (0,+ \infty) \).
It is easy to verify that \( f \)
is non-decreasing on \( (1, + \infty) \)
and that \( f(x)=f\left(\frac1x\right) \) for every \( x> 0 \).
Furthermore from the given conditions it follows that
only \( x_1 \) can be less than \( 1 \) and that
\( \frac1{1+x_2} \leq 1- \frac1{1+x_1} = \frac{x_1}{1+x_1} \).
Hence \( x_2\geq \frac1{x_1} \). Now it is clear
that (in both of the cases
\( x_1 \geq 1 \) and \( x_1< 1 \)):
\[ f(x_1)=f\left(\frac1{x_1}\right) \leq f(x_1)\leq \cdots \leq
f(x_n).\] This means that the sequence
\( \left(\frac{1+x_k}{x_k}\right)_{k=1}^n \) is non-decreasing.
Thus according to the Chebyshev’s inequality we have:
\begin{eqnarray}&&\nonumber
\left(\frac{1+x_1}{\sqrt{x_1}} + \cdots +
\frac{1+x_n}{\sqrt{x_n}}\right) \left(\frac1{1+x_1} +
\frac1{1+x_2}+ \cdots + \frac1{1+x_n}\right)\\
\nonumber &\geq& n\cdot
\left(\frac1{\sqrt{x_1}}+ \frac1{\sqrt{x_2}} + \cdots +
\frac1{\sqrt{x_n}}\right).
\end{eqnarray} The equality holds if and only if
\( \frac{1}{1+x_1} = \cdots = \frac1{1+x_n} \), or
\( \frac{1+x_1}{\sqrt{x_1}}=\cdots = \frac{1+x_n}{\sqrt{x_n}}, \)
which implies that \( x_1=x_2 = \cdots = x_n \).
Thus the equality holds if and only if \( x_1=\cdots =
x_n=n-1 \).