# A recursive sequence generated by a polynomial

Let $P(x)$ be a polynomial in one variable with integer coefficients, and define the sequence $a_0, a_1, a_2, a_3,\cdots$ $$a_0 = 0, \ a_n = P(a_{n-1})$$ If there exists a $m$ natural number such that $a_m = 0$, then $a_1 =0$ or $a_2 = 0$.

I have headache with this problem, my attempts go nowhere.

Can you help me?

-
Here's a start anyways: First of all, note that each $a_n$ is an integer. Thus, if $a_m=0$, $a_{m-1}$ is a root of $P$. In particular, $P$ has an integral root. By the Rational Root Theorem, this implies that either the constant term of $P$ is $0$ or a factor of the constant term is a root of $P$. However, $a_1=P(a_0)=P(0)$ is the constant term of $P$, so in the first case $a_1=0$ and we are done, so suppose instead that the constant term is nonzero and a factor of it is a root of $P$. –  Jonathan Gleason May 9 '12 at 0:51

This is essentially a consequence of the fact that $(x - y)\mid P(x) - P(y)$. This implies that $$(a_{n+1}-a_n)\mid (P(a_{n+1})- P(a_n)) = a_{n+2} - a_{n+1}$$ for all $n\geq 0$. Thus you get that $$a_1 - a_0\mid a_2 - a_1 \mid a_3 - a_2\cdots.$$ If there is an $m$ such that $a_m = 0$, this guarantees the sequence $a_{n+1} - a_n$ is periodic. That is, you have a cycle of integers all of which divide the next. This is only possible if each of the integers is $0$ or if each of the integers is $\pm 1$. In the case they are all $0$, you get $a_1 = 0$, which is one of the posible outcomes. Suppose that all the integers are $\pm 1$. In this case, we want to conclude that $a_2 = 0$. Indeed, if $a_2\neq 0$, then either [Case 1] $a_2 = 2$ and $a_1 = 1$ or [Case 2] $a_2 = -2$ and $a_1 = -1$. Since $a_{n+1}$ can only differ by $\pm 1$ from $a_n$, the only way to have $a_m = 0$ for $m>0$ is for $a_{m-1} = 1$ (in case 1) or for $a_{m-1} = -1$ (in case 2). But if $a_{m-1} = 1$, then $a_m = P(a_{m-1}) = P(1) = a_2 = 2\neq 0,$ a contradiction. Similarly, if $a_{m-1} = -1$, then $a_m = P(a_{m-1}) = P(-1) = a_2 = -2$, a contradiction.

-

This is Problem A-6 on the 61st William Lowell Putnam Competition (2000); you'll find a complete set of answers to the 2000 Putnam here. (In fact solutions are available for the years 1995-2011.)

Kiran S. Kedlaya, Bjorn Poonen, Ravi Vakil, The William Lowell Putnam Mathematical Competition 1985-2000 gives another solution as well, which I adapt slightly.

Choose $m\ge 1$ minimal such that $a_m=0$. If $m=1$, we're done, so assume that $m>1$. An easy induction shows that $x_n=x_{n\,\bmod\,m}$ for all $n\ge 0$. Suppose that $0\le i<j<m$; then $$P^{m-j}(x_i)=P^{m-j}(x_j)=x_m=0\;,$$ contradicting the minimality of $m$, so the numbers $x_0,\dots,x_{m-1}$ are distinct, and in general we have $x_j=x_k$ iff $j\equiv k\pmod m$. (Here $P^n=\underbrace{P\circ P\circ\ldots\circ P}_n$.)

Now $x_j=\min\{x_0,\dots,x_{m-1}\}$ and $x_k=\max\{x_0,\dots,x_{m-1}\}$. Then $$x_k-x_j\mid P(x_k)-P(x_j)=x_{k+1}-x_{j+1}\ne 0\;,$$ since $j+1\not\equiv k+1\pmod m$. On the other hand, $x_k-x_j\ge|x_{k+1}-x_{j+1}|$ by the choice of $j$ and $k$, so $x_k-x_j=|x_{k+1}-x_{j+1}|$, and $\{x_j,x_k\}=\{x_{j+1},x_{k+1}\}$. But $x_{j+1}\ne x_j$, since $m>1$, so $x_{j+1}=x_k$, and hence $x_{j+2}=x_{k+1}=x_j$. But then $j+2\equiv j\pmod m$, so $m\mid 2$, and therefore $m=2$, as desired.

-