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_{1}, ... , 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.

© John Scholes

jscholes@kalva.demon.co.uk

25 Jan 2002