aij are reals in [0, 1]. Show that ( ∑i=1n ∑j=1mi aij/i )2 ≤ 2m ∑i=1n ∑j=1mi aij.
The question looks incredibly complicated, but is actually easy. We just use induction and the fact that each aij ≤ 1.
Put bi = ∑1mi aij. Notice that since each aij ≤ 1, we have bi ≤ mi. We use induction on n. For n = 1, the required result is: b12 ≤ 2mb1. But b1 ≤ m and b1 ≥ 0, so this is certainly true.
Now assume the result is true for n.
For n + 1, the lhs is (b1/1 + b2/2 + ... + bn/n)2 + 2(b1/1 + ... + bn/n) bn+1/(n+1) + bn+12/(n+1)2, and the rhs is 2m(b1 + ... + bn) + 2mbn+1. Given the result for n, it is sufficient to show that: 2(b1/1 + ... + bn/n) bn+1/(n+1) + bn+12/(n+1)2 ≤ 2mbn+1. Divding by bn+1 and using bi/i le; m, we need: 2nm/(n+1) + m/(n+1) ≤ 2m, which is clearly true.
39th Putnam 1978
© John Scholes
30 Nov 1999