Define an by a0 = α, an+1 = 2an - n2. For which α are all an positive?
Answer: α ≥ 3.
The trick is that we can solve the recurrence relation. A particular solution is obviously a polynomial with leading term n2, so we soon find an = n2 + 2n + 3. The general solution is then an = n2 + 2n + 3 + k2n. The initial condition a0 = α gives that k = α - 3. A necessary and sufficient condition for all an to be positive is evidently k ≥ 0, or α ≥ 3.
41st Putnam 1980
© John Scholes
10 Dec 1999
Last corrected/updated 21 Nov 02