Putnam 1983/B4 solution

44th Putnam 1983

Problem B4

Let f(n) = n + [√n]. Define the sequence a_i by a₀ = m, a_n+1 = f(a_n). Prove that it contains at least one square.

Solution

Suppose m = n² + r, with 1 ≤ r ≤ n. Then [√m] = n, so a₁ = n² + n + r. We still have [√(n² + n + r)] = n (because the next square up is n² + 2n + 1), so a₂ = n² + 2n + r = (n + 1)² + (r - 1). Thus if r = 1, then a₂ is a square, and by a simple induction in the general case a_2r is a square.

Now if n+1 ≤ r < 2n+1, then we still have a₁ = n² + n + r = (n + 1)² + (r - n - 1) and 0 ≤ (r - n - 1) < n. If r = 0, then we have a square. If not, then a further 2(r - n - 1) steps give a square.

44th Putnam 1983