Let $a_1, b_1, a_2, b_2, \dots , a_n, b_n$ be nonnegative real numbers. Prove that
$$\sum_{i, j = 1}^{n} \min\{a_ia_j, b_ib_j\} \le \sum_{i, j = 1}^{n} \min\{a_ib_j, a_jb_i\}.$$
How do I prove this inequality. I have studied only basic inequalities, namely AM-GM, CS inequality and Tchebycheff's inequality. How do I incorporate that condition of minimum of the two chosen numbers and prove the inequality using the above ones
?
Best Answer
It's USA 2000. The following solution is not mine.
Since if $\min\{a_i,b_i\}=0$ then $\min\{a_ia_j,b_ib_j\}=\min\{a_ib_j,a_jb_i\}=0,$
we can assume that $a_i>0$ and $b_i>0$.
Lemma 1.
Let $r_i\geq0$ and $x_i$ be real numbers. Prove that: $$\sum_{i,j=1}^n\min\{r_i,r_j\}x_ix_j\geq0.$$ Proof.
Since $\min\{r_i,r_j\}=\min\{r_j,r_i\},$ we can assume that $0=r_0\leq r_1\leq r_2\leq...\leq r_n$ and we obtain: $$\sum_{i,j=1}^n\min\{r_i,r_j\}x_ix_j=\sum_{i=1}^nr_ix_i^2+2\sum_{1\leq i<j\leq n}r_ix_ix_j=\sum_{i=1}^n\left(r_i-r_{i-1}\right)\left(\sum_{j=i}^nx_j\right)^2\geq0.$$ Lemma 2.
Let $a_i>0$, $b_i>0$, $r_i=\frac{\max\{a_i,b_i\}}{\min\{a_i,b_i\}}-1$ and $x_i=sign(a_i-b_i)\min\{a_i,b_i\}.$ Prove that: $$\min\{a_ib_j,a_jb_i\}-\min\{a_ia_j,b_ib_j\}=\min\{r_i,r_j\}x_ix_j.$$ Proof.
Since replacing $a_i$ with $b_i$ gives replacing signs of the both sides, we can assume that $a_i\geq b_i$.
Similarly, we can assume that $a_j\geq b_j$ and we obtain: $$\min\{r_i,r_j\}x_ix_j=\min\left\{\frac{a_i}{b_i}-1,\frac{a_j}{b_j}-1\right\}b_ib_j=$$ $$=\min\{a_ib_j-b_ib_j,a_jb_i-b_ib_j\}=\min\{a_ib_j,a_jb_i\}-b_ib_j=$$ $$=\min\{a_ib_j,a_jb_i\}-\min\{a_ia_j,b_ib_j\}.$$ Now, by applying of these lemmas we obtain: $$\sum_{i,j=1}^n\min\{a_ib_j,a_jb_i\}-\sum_{i,j=1}^n\min\{a_ia_j,b_ib_j\}=$$ $$=\sum_{i,j=1}^n\left(\min\{a_ib_j,a_jb_i\}-\min\{a_ia_j,b_ib_j\}\right)=\sum_{i,j=1}^n\min\{r_i,r_j\}x_ix_j\geq0$$ and we are done!
For $n=4$ we obtain: $$(r_4-r_3)x_4^2+(r_3-r_2)(x_3+x_4)^2+(r_2-r_1)(x_2+x_3+x_4)^2+(r_1-r_0)(x_1+x_2+x_3+x_4)^2=$$ $$=r_1x_1^2+(r_2-r_1+r_1)x_2^2+(r_3-r_2+r_2-r_1+r_1)x_3^2+(r_4-r_3+r_3-r_2+r_2-r_1+r_1)x_4^2+$$ $$+2r_1x_1x_2+2r_1x_1x_3+2r_1x_1x_4+2(r_2-r_1+r_1)x_2x_3+$$ $$+2(r_2-r_1+r_1)x_2x_4+2(r_3-r_2+r_2-r_1+r_1)x_3x_4=$$ $$=r_1x_1^2+r_2x_2^2+x_3r_3^2+r_4x_4^2+2r_1x_1x_2+2r_1x_1x_3+2r_1x_1x_4+$$ $$+2r_2x_2x_3+2r_2x_2x_4+2r_3x_3x_4.$$