p(x) is a polynomial with integer coefficients. A sequence x_{0}, x_{1}, x_{2}, ... is defined by x_{0} = 0, x_{n+1} = p(x_{n}). Prove that if x_{n} = 0 for some n > 0, then x_{1} = 0 or x_{2} = 0.

**Solution**

If x_{1} = 0, then obviously all x_{n} = 0. So that is one possibility. Assume, then, that x_{1} is non-zero. Assume also that x_{N} = 0 for some N > 1. Then x_{N+1} = p(0) = x_{1}.

a - b always divides a^{s} - b^{s} and hence also p(a) - p(b). So x_{n+1} - x_{n} divides x_{n+2} - x_{n+1}. But x_{N+1} - x_{N} = x_{1} - x_{0}. So for all 0 <= n <= N, we have x_{n+1} - x_{n} = ±x_{1}. Moreover, some signs must be positive and some negative, since (x_{1} - x_{0}) + (x_{2} - x_{1}) + ... + (x_{N} - x_{N-1}) = x_{N} - x_{0} = 0. So we must be able to find an adjacent pair of opposite signs: x_{n+1} - x_{n} = -(x_{n} - x_{n-1}), with 1 ≤ n ≤ N. Hence x_{n-1} = x_{n+1}. But now p(x_{n-1}) = p(x_{n+1}), or x_{n} = x_{n+2}. So by a simple induction x_{N} = x_{N+2}. But x_{N} = 0, and x_{N+2} = x_{2}, so x_{2} = 0, as required.

© John Scholes

jscholes@kalva.demon.co.uk

1 Jan 2001