Una secuencia recurrente generada por un polinomio

Question

Que $P(x)$ ser un polinomio en una variable con coeficientes del número entero y definir la secuencia $a_0, a_1, a_2, a_3,\cdots$ $$a_0 = 0, \ a_n = P(a_{n-1})$ $If allí existe un $m$ número natural tal que $a_m = 0$ y $a_1 =0 $ o $a_2 = 0$.

Tengo dolor de cabeza con este problema, mis intentos de ir a ninguna parte.

¿Me puedes ayudar?

Answer 1

Esto es esencialmente una consecuencia del hecho de que el $(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$, una contradicción.

Answer 2

Este es el Problema a-6 en la 61ª William Lowell Putnam Competencia (2000); encontrarás un completo conjunto de respuestas a las 2000 Putnam aquí. (De hecho, las soluciones están disponibles para los años 1995-2011.)

Kiran S. Kedlaya, Bjorn Poonen, Ravi Vakil, El William Lowell Putnam Competencia de Matemáticas 1985-2000 da otra solución, que hay que adaptarse un poco.

Elija $m\ge 1$ mínima tal que $a_m=0$. Si $m=1$, hemos terminado, así que asumir que $m>1$. Un fácil de inducción muestra que $x_n=x_{n\,\bmod\,m}$ todos los $n\ge 0$. Supongamos que $0\le i<j<m$; a continuación,$$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$.)

Ahora$x_j=\min\{x_0,\dots,x_{m-1}\}$$x_k=\max\{x_0,\dots,x_{m-1}\}$. Entonces $$x_k-x_j\mid P(x_k)-P(x_j)=x_{k+1}-x_{j+1}\ne 0\;,$$ since $j+1\no\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$, como se desee.