MathLabs

Problem 2

Show that the inequality ∑i=1n∑j=1n∣xi−xj∣≤∑i=1n∑j=1n∣xi+xj∣\sum_{i=1}^n\sum_{j=1}^n\sqrt{|x_i-x_j|}\le\sum_{i=1}^n\sum_{j=1}^n\sqrt{|x_i+x_j|} holds for all real numbers x1,x2,…,xnx_1,x_2,\ldots,x_n.
Step 5 of 5: Case t=−xi+xj2t=-\tfrac{x_i+x_j}{2}: delete a pair and induct
Previous stepNext step
t=−xi+xj2 ⇒ xi+t=−(xj+t)t=-\tfrac{x_i+x_j}{2}\ \Rightarrow\ x_i+t=-(x_j+t)
Detailed analysis

If instead the minimum occurs at t=−xi+xj2t=-\tfrac{x_i+x_j}{2}, then after shifting, xi+t=−(xj+t)x_i+t=-(x_j+t), so swapping the labels ii and jj leaves every term ∣xp+xq+2t∣\sqrt{|x_p+x_q+2t|} involving ii or jj unchanged as a multiset while turning it into the matching term of ∑p,q∣xp−xq∣\sum_{p,q}\sqrt{|x_p-x_q|}; the rows and columns indexed by i,ji,j again match on both sides, and deleting both variables reduces the inequality to n−2n-2 variables, completing the induction and the proof.