30th Putnam 1969

Problem B5

The sequence ai, i = 1, 2, 3, ... is strictly monotonic increasing and the sum of its inverses converges. Let f(x) = the largest i such that ai < x. Prove that f(x)/x tends to 0 as x tends to infinity.



Suppose not. Then for some fixed k > 0, we can find arbitrarily large x such that f(x) > kx. So take a sequence x1 < x2 < x3 < ... such that (1) f(xi) > kxi, (2) kxi/2 gt; f(xi-1). Then by (1) at least kxi members of the sequence an are less than xi. By (2) at most kxi/2 are less than xi-1. So at least kxi/2 must lie between xi-1 and xi.

So ∑ 1/an has at least kxi/2 terms between 1/xi and 1/xi-1. These terms sum to at least k/2. All terms are positive, so the series diverges. Contradiction.



30th Putnam 1969

© John Scholes
14 Jan 2002