p(x) is a polynomial with integer coefficients. A sequence x0, x1, x2, ... is defined by x0 = 0, xn+1 = p(xn). Prove that if xn = 0 for some n > 0, then x1 = 0 or x2 = 0.
If x1 = 0, then obviously all xn = 0. So that is one possibility. Assume, then, that x1 is non-zero. Assume also that xN = 0 for some N > 1. Then xN+1 = p(0) = x1.
a - b always divides as - bs and hence also p(a) - p(b). So xn+1 - xn divides xn+2 - xn+1. But xN+1 - xN = x1 - x0. So for all 0 <= n <= N, we have xn+1 - xn = ±x1. Moreover, some signs must be positive and some negative, since (x1 - x0) + (x2 - x1) + ... + (xN - xN-1) = xN - x0 = 0. So we must be able to find an adjacent pair of opposite signs: xn+1 - xn = -(xn - xn-1), with 1 ≤ n ≤ N. Hence xn-1 = xn+1. But now p(xn-1) = p(xn+1), or xn = xn+2. So by a simple induction xN = xN+2. But xN = 0, and xN+2 = x2, so x2 = 0, as required.
61st Putnam 2000
© John Scholes
1 Jan 2001