Putnam 2000, Problem A-6

Let $f(x)$ be a polynomial with integer coefficients. Define a sequence $a_0, a_1, \ldots$ of integers such that $a_0 = 0$ and $a_{n+1} = f(a_n)$ for all $n \geq 0$. Prove that if there exists a positive integer $m$ for which $a_m = 0$ then either $a_1 = 0$ or $a_2 = 0$.

Solution:
Recall that if \(f(x)\) is a polynomial with integer coefficients, then \(m - n\) divides \(f(m) - f(n)\) for any integers \(m\) and \(n\). In particular, if we put \(b_n = a_{n+1} - a_n\), then \(b_n\) divides \(b_{n+1}\) for all \(n\). On the other hand, we are given that \(a_0 = a_m = 0\), which implies that \(a_1 = a_{m+1}\) and so \(b_0 = b_m\). If \(b_0 = 0\), then \(a_0 = a_1 = \cdots = a_m\) and we are done. Otherwise, \(|b_0| = |b_1| = \cdots = |b_n| = \pm b_0\) for all \(n\).  

Now \(b_0 + \cdots + b_{m-1} = a_m - a_0 = 0\), so half of the integers \(b_0, \ldots, b_{m-1}\) are positive and half are negative. In particular, there exists an integer \(0 < k < m\) such that \(b_{k-1} = -b_k\), which is to say, \(a_{k-1} = a_{k+1}\). From this it follows that \(a_n = a_{n+2}\) for all \(n \geq k - 1\); in particular, for \(m = n\), we have  
\[
a_0 = a_m = a_{m+2} = f(f(a_0)) = a_2.
\]