proof of Chebyshev’s inequality

Let $x_1,x_2,\mathrm{\dots },x_n$ and $y_1,y_2,\mathrm{\dots },y_n$ be real numbers suchthat $x_1\le x_2\le \mathrm{\cdots }\le x_n$. Write the product$(x_1+x_2+\mathrm{\cdots }+x_n)(y_1+y_2+\mathrm{\cdots }+y_n)$ as

$(x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n)$(1)

$+$$(x_1{y}_2+x_2{y}_3+\mathrm{\cdots }+x_{n-1}{y}_n+x_n{y}_1)$

$+$$(x_1{y}_3+x_2{y}_4+\mathrm{\cdots }+x_{n-2}{y}_n+x_{n-1}{y}_1+x_n{y}_2)$

$+$$\mathrm{\cdots }$

$+$$(x_1{y}_n+x_2{y}_1+x_3{y}_2+\mathrm{\cdots }+x_n{y}_{n-1}).$

• If $y_1\le y_2\le \mathrm{\cdots }\le y_n$, each of the $n$ terms in parenthesesis less than or equal to $x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n$, according tothe rearrangement inequality. From this, it follows that

  $$(x_1+x_2+\mathrm{\cdots }+x_n)(y_1+y_2+\mathrm{\cdots }+y_n)\le n(x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n)$$

  or (dividing by $n^2$)

  $$\left(\frac{x_1+x_2+\mathrm{\cdots }+x_n}{n}\right)\left(\frac{y_1+y_2+\mathrm{\cdots }+y_n}{n}\right)\le \frac{x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n}{n}.$$

• If $y_1\ge y_2\ge \mathrm{\cdots }\ge y_n$, the same reasoning gives

  $$\left(\frac{x_1+x_2+\mathrm{\cdots }+x_n}{n}\right)\left(\frac{y_1+y_2+\mathrm{\cdots }+y_n}{n}\right)\ge \frac{x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n}{n}.$$

It is clear that equality holds if $x_1=x_2=\mathrm{\cdots }=x_n$ or$y_1=y_2=\mathrm{\cdots }=y_n$. To see that this condition is also necessary,suppose that not all $y_i$’s are equal, so that $y_1\ne y_n$.Then the second term in parentheses of (1) can only beequal to $x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n$ if $x_{n-1}=x_n$, the thirdterm only if $x_{n-2}=x_{n-1}$, and so on, until the last term whichcan only be equal to $x_1{y}_1+x_2{y}_2+\mathrm{\cdots }+x_n{y}_n$ if $x_1=x_2$. Thisimplies that $x_1=x_2=\mathrm{\cdots }=x_n$. Therefore, Chebyshev’s inequalityis an equality if and only if $x_1=x_2=\mathrm{\cdots }=x_n$ or$y_1=y_2=\mathrm{\cdots }=y_n$.