### 25th Putnam 1964

Problem B1

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

Solution

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

The idea is to take N' > N with bN' > kN' and to ensure that half the indices i with ai ≤ 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/ai 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/ai, 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.