Putnam 1966/A6 solution

27th Putnam 1966

Problem A6

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

Solution

Clearly a_n < a_n+1. Also, if we replace the final (1 + n) in a_n by (1 + n)², then a simple induction shows that the resulting expression simplifies to 3. Hence a_n < 3. An increasing sequence which is bounded above must converge. So a_n 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)² = 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)² ≥ 1/2 (x² + 2x) + 1 > 1/2 (x + 1)², 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.

27th Putnam 1966