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 4 of 5: Case t=−xit=-x_i: delete one variable and induct
Previous stepNext step
t=−xi ⇒ xi+t=0t=-x_i\ \Rightarrow\ x_i+t=0
Detailed analysis

If the minimum occurs at t=−xit=-x_i, then after the shift the ii-th variable equals 00, and the row and column of FF indexed by ii contribute 2∑j∣xj∣2\sum_{j}\sqrt{|x_j|}, exactly matching the corresponding row and column of ∑p,q∣xp−xq∣\sum_{p,q}\sqrt{|x_p-x_q|}; cancelling these equal contributions reduces the inequality to the same statement for the remaining n−1n-1 variables, which holds by the induction hypothesis.