Rearrangement Inequality. Chebyshev’s Inequality

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.\]

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.

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).

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*}

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\).

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). \]

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*}

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\).