25th Putnam 1964

a_n are positive integers such that ∑ 1/a_n converges. b_n is the number of a_n which are <= n. Prove lim b_n/n = 0.

Solution

If not, then for some k > 0 we can find arbitrarily large N such that b_N > kN. Then at least kN of the integers a₁, ... , a_N do not exceed N. Let S be the set of indices i from 1, 2, ... N with a_i ≤ N. Then since S has at least kN members, the sum over S of 1/a_i is at least k.

The idea is to take N' > N with b_N' > kN' and to ensure that half the indices i with a_i ≤ N' were not included in S. Take S' to be these new indices. Then since S' does not overlap S, the sum over S and S' of 1/a_i is at least k + k/2. We then repeat always choosing the new set of indices not to overlap any of the previous sets. So at each stage we will add k/2 to the sum of 1/a_i, which must therefore diverge, establishing a contradiction.

We can do this by taking the successor N' to N sufficiently big. In fact, it is sufficient to take N'/2 > N/k because we know that all of the previous index sets are contained in {1, 2, ... , N}, so to avoid them we do not have to drop more than N < kN'/2 indices, leaving at least kN'/2 new indices.

25th Putnam 1964

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