x1 < x2 < ... < xn are real numbers, where n > 2. Show that n(n-1)/2 Si<j xixj > ( (n-1)x1 + (n-2)x2 + ... + 2xn-2 + xn-1) (x2 + 2x3 + ... + (n-1)xn).
Solution
Put yi = (xi+1 + xi+2 + ... + xn), y = (x2 + 2x3 + ... + (n-1)xn), c = n(n-1)/2, zi = cyi - (n-i)y. Then n(n-1)/2 Si<j xixj - ( (n-1)x1 + (n-2)x2 + ... + 2xn-2 + xn-1) (x2 + 2x3 + ... + (n-1)xn) = c(x1y1 + x2y2 + ... + xn-1yn-1) - y( (n-1)x1 + (n-2)x2 + ... + xn-1) = (x1z1 + x2z2 + ... + xn-1zn-1) (*).
We have y1 + y2 + ... + yn-1 = (x2 + ... + xn) + (x3 + ... + xn) + ... + xn = y. Also (n-1) + (n-2) + ... + 1 = c, so z1 + ... + zn-1 = 0. We have y = x2 + 2x3 + ... + (n-1)xn < xn + 2xn + ... + (n-1)xn = cxn. So zn-1 = cyn-1 - y = cxn - y > 0. So at least one zi is negative.
zi+1/( c(n-i-1) ) - zi/( c(n-i) ) = yi+1/(n-i-1) - yi/(n-i). But yi+1/(n-i-1) is the average of the terms xi+2, ... , xn and yi/(n-i) is the average of the terms xi+1, ... , xn and xi is a strictly increasing sequence. Hence zi+1/( c(n-i-1) ) > zi/( c(n-i) ). So for some k we must have zi <= 0 for i = 1, 2, ... , k and zi > 0 for i = k+1, ... , n-1. Hence (xi - xk) zi >= 0 for all i and it is strictly positive for i = n-1 (and possibly other i also). Hence (x1z1 + x2z2 + ... + xn-1zn-1) > xk(z1 + ... + zn-1) = 0. With (*) this gives the required inequality.
(C) John Scholes
jscholes@kalva.demon.co.uk
4 Sep 2002