0 = a1, a2, a3, ... is a non-decreasing, unbounded sequence of non-negative integers. Let the number of members of the sequence not exceeding n be bn. Prove that (x0 + x1 + ... + xm)(y0 + y1 + ... + yn) ≥ (m + 1)(n + 1).
Solution
If xm = 0, then y0 ≥ m+1 and so all of y0, y1, ... , yn ≥ m+1, so the inequality holds. If xm > 0, then let xk be the first non-zero term and suppose xk = h > 0. Reduce xk to 0. Then ∑xi is reduced by h. Each of y0, y1, ... , yh-1 is increased by 1 and the other yj are unchanged, so ∑yj is increased by at most h. Hence ∑xi + ∑yj is not increased. Repeat until we reach xm = 0. Then the resulting inequality is true. We have not increased the lhs and the rhs is unchanged, so the orignal inequality was true.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002