Putnam 1985/A3 solution

46th Putnam 1985

Problem A3

x is a real. Define a_{i 0} = x/2ⁱ, a_{i j+1} = a_{i j}² + 2 a_{i j}. What is lim_n→∞ a_{n n}?

Solution

Answer: e^x - 1.

a_{n+1 n} for x is the same as a_{n n} for x/2. So if we write a_{n n} as p_n(x) then evidently p_n is a polynomial and we have the relation p_n+1(x) = 2p_n(x/2) + p_n(x/2)² (*) and also p₀(x) = x.

If we add 1 to both sides of (*), then it becomes 1 + p_n+1(x) = (1 + p_n(x/2) )². Iterating: 1 + p_n(x) = (1 + x/N)^N, where N = 2ⁿ. But lim (1 + x/n)ⁿ = e^x as n → ∞, so p_n(x) → e^x - 1.

46th Putnam 1985