### 24th Putnam 1963

Problem A4

Show that for any sequence of positive reals, an, we have lim supn→∞ n( (an+1 + 1)/an - 1) ≥ 1. Show that we can find a sequence where equality holds.

Solution

Suppose lim sup < 1. Then we cannot find an infinite subsequence with n( (an+1 + 1)/an - 1) ≥ 1, so we must have n( (an+1 + 1)/an - 1) < 1 for all sufficiently large n. Suppose it is true for all n ≥ N. Then (aN+1 + 1)/aN < (N + 1)/N and hence aN/N > (aN+1 + 1)/(N + 1) = aN+1/(N+1) + 1/(N+1). But similarly, aN+1/(N+1) > aN+2/(N+2) + 1/(N+2) and so on. Hence aN ≥ 1/(N+1) + 1/(N+2) + ... , which is impossible since the rhs diverges. So we have established that lim sup ≥ 1.

We can experiment with various series. an = n gives 2. an = n2 also gives 2. Higher powers give higher values. So we try looking at exponents between 1 and 2. an = n1+k gives 1+k. So by taking k arbitrarily small we can get close to 1, but we cannot reach it. It is often helpful to think of log n as nk with k infinitesimally small. So we try an = n log n. That gives n( (an+1 + 1)/an - 1) = (1 + n log (1 + 1/n) + log(n + 1) )/log n = (1 + n log (1 + 1/n) + (log(1 + 1/n) )/log n + 1. But 1 + n log(1 + 1/n) + log (1 + 1/n) is bounded and so n( (an+1 + 1)/an - 1) has limit 1 (and hence also lim sup = 1).