### 27th Putnam 1966

Problem A6

Let an = √(1 + 2 √(1 + 3 √(1 + 4 √(1 + 5 √( ... + (n - 1) √(1 + n) ... ) ) ) ) ). Prove lim an = 3.

Solution

Clearly an < an+1. Also, if we replace the final (1 + n) in an by (1 + n)2, then a simple induction shows that the resulting expression simplifies to 3. Hence an < 3. An increasing sequence which is bounded above must converge. So an tends to a limit which is at most 3.

However, it is harder to show that the limit is 3. We need a new idea. Put f(x) = lim √(1 + x √(1 + (x+1) √(1 + (x+2) √(1 + (x+3) √( ... + (x+n-1) √(1 + x+n) ... ) ) ) ) ). Then we may guess that f(x) = x + 1. The same idea as before shows that f(x) exists and is at most x + 1. Also, we have that f(x)2 = x f(x+1) + 1 (*).

The trick is that a crude lower limit works, because we can use (*) to refine it repeatedly. Removing all the 1s and replacing (x+1), (x+2) ... by x gives that f(x) ≥ lim √( x √( x √( x √( x ... )))) = x > 1/2 (x + 1). Now (*) gives f(x)2 ≥ 1/2 (x2 + 2x) + 1 > 1/2 (x + 1)2, so f(x) > (x + 1)√(1/2). Using (*) again gives f(x) > (x + 1) (1/2)1/4 and so on. Hence f(x) ≥ x + 1 as required.