Let f(n) = n + [√n]. Define the sequence a_{i} by a_{0} = m, a_{n+1} = f(a_{n}). Prove that it contains at least one square.

**Solution**

Suppose m = n^{2} + r, with 1 ≤ r ≤ n. Then [√m] = n, so a_{1} = n^{2} + n + r. We still have [√(n^{2} + n + r)] = n (because the next square up is n^{2} + 2n + 1), so a_{2} = n^{2} + 2n + r = (n + 1)^{2} + (r - 1). Thus if r = 1, then a_{2} 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_{1} = n^{2} + n + r = (n + 1)^{2} + (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.

© John Scholes

jscholes@kalva.demon.co.uk

16 Jan 2001