Let $P(x)$ be a polynomial with integer coefficients. Define a sequence ${a_n}$ by $a_0 = 0$ and $a_{n} = P(a_{n-1})$ for all $n \geq 1.$ Prove that if there exists a positive integer $m$ for which $a_m = 0,$ then $a_1 = 0$ or $a_2 = 0.$
Problem
Source: Hong Kong TST - HKTST 2022 2.2
Tags: algebra, polynomial
21.07.2024 20:33
Easy one Assume not , Then $0 -> P(0) -> P^2(0) -> ... -> P^{m-1}(0) -> 0$ is a cycle for some $m\geq 3$. Note that if the members of this cycle were $a_0, a_1, \cdots, a_{m-1}$, with $a_0=0$, then $a_i - a_{i-1} \mid a_{i+1} - a_i$ for all $0\leq i\leq m-1$ ( Indices taken mod $m$), Becaue of famous lenma : a-b | P(a)-P(b). However, this means $a_1-a_0 \mid a_2 -a_1 \mid \cdots \mid a_0 - a_{m-1} \mid a_1-a_0$, so all the $a_{i+1}-a_i$ must be the same Abolute value of $a_1-a_0$. Suppose $a_1-a_0 = d$, then you do $+d$ or $-d$ every time. Now, by definition $a_1 = d$. Now, $a_2 = 2d$, since otherwise $a_2=d-d=0$, which is bad because of our assumption of the contrary. ($m-1 \geq 2$). Now, note that we must have $a_3 = 3d$, since otherwise $a_3 = d$, but This contradicts the fact that our cycle has length $\geq 3$. Similarly, we get $a_4 = 4d$, $a_5 = 5d$, etc., by induction ( Since otherwise we get $a_m = a_{m+2}$ which is contradicting fact that our cycle has length $\geq 3$). But then $a_{m-1} = (m-1)d$, so $a_0 = 0 \in \{md, (m-2)d\}$, but since $m\geq 3$, this is absurd. So contradiction!!!!!!!!!!