The real numbers x1, x2, x3, ... satisfy xi+j <= xi + xj for all i, j. Prove that x1 + x2/2 + ... + xn/n >= xn.
Solution
We use induction. Suppose the result is true for n. We have:
x1 >= x1
x1 + x2/2 >= x2
...
x1 + x2/2 + ... + xn/n >= xn
Also: x1 + 2x2/2 + ... + nxn/n = x1 + ... + xn
Adding: (n+1) x1 + (n+1)x2/2 + ... + (n+1)xn/n >= 2(x1 + ... + xn). But rhs = (x1 + xn) + (x2 + xn-1) + ... + (xn + x1) >= n xn+1. Hence result.
(C) John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002