30th Putnam 1969

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

Solution

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

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

30th Putnam 1969

© John Scholes
jscholes@kalva.demon.co.uk
14 Jan 2002