# Prove that either $a_1 =0$ or $a_2 =0$.

I was having a look at this question

Let $$f$$ be a polynomial with integer coefficients. Define $$a_1 = f(0);~~a_2= f(a_1) = f(f(0))$$ and $$a_n = f(a_{n-1})$$ for $$n \geq 3$$. If there exists a natural number $$k \geq 3$$ such that $$a_k = 0$$, then prove that either $$a_1 = 0$$ or $$a_2= 0$$

Source: ISI B-MATH UGB 2019 paper

And at first glance I couldn't understand whether $$a_i$$'s were the coefficients of the given polynomial or they are some separate sequence. After some time I came to the conclusion that the latter is correct. I have tried to prove it, but in need of some validation so as to confirm if my proof is free from flaws. The solution which I have done is quite long, so if it makes the question hard to read then please let me know in the comments and I shall post it as answer. Any other answer with some different idea is also welcome (but it has to be a full solution).

Let $$k$$ be the least number such that $$a_k = 0$$ in the sequence $$a_1, a_2 , a_3 \cdots$$. $$a_k = 0 \implies P(a_k) = P(0) = a_1$$ $$P(a_{k-1}) = a_k \implies P(a_{k-1}) = 0$$ As $$P(x)$$ is a polynomial with integer coefficients, therefore $$P(0)$$ will be an integer and hence $$a_1 \in \mathbb{Z}$$.

By the same argument, $$P(a_1) = a_2 \in \mathbb{Z}, P(a_2) = a_3 \in \mathbb{Z}$$, that is $$a_i \in \mathbb{Z}$$.

It is a well know theorem that if $$P(x)$$ is a polynomial with integer coefficients, then if $$a, b \in \mathbb{Z}$$ implies $$(a-b) \big| \left(P(a)- P(b)\right)$$.

Applying the above theorem continuously $$a_1 \big| P(a_1)- P(0) \implies a_1 \big| a_2 - a_1 \implies |a_1| \leq |a_2 - a_1 |$$ $$a_2 - a_1 \big| P(a_2) - P(a_1) \implies a_2 -a_1 \big| a_3 -a_2 \implies |a_2 -a_1 | \leq |a_3 - a_2|$$ $$\cdots$$ $$a_ k - a_{k-1} \big| P(a_k) - P(a_{k-1}) \implies (-a_{k-1}) \big| a_1 \implies|a_{k-1}| \leq |a_1|$$

$$|a_1 | \leq |a_2 -a_1 | \leq |a_3 - a_2| \leq \cdots \leq |a_{k-1}| \leq |a_1|$$ As, $$|a_{k-1}|$$ is greater than/equal to and less than/equal to $$|a_1|$$ therefore, to avoid contradiction we have to have $$|a_1| = |a_2 -a_1| = |a_3 - a_2| \cdots = |a_{k-1}|$$

We notice that if in above it ever happens that $$a_i - a_{i-1} = - \left( a_{i+1} - a_{i}\right)$$ then we will get : $$a_i - a_{i-1} = a_i - a_{i+1}$$ $$a_{i-1} = a_{i+1}$$ $$P (a_{i-1}) = P(a_{i+1}) \implies a_i = a_{i+2}$$ $$P(a_i)= P(a_{i+2}) \implies a_{i+1} = a_{i+3}$$ And the process continues until we get $$a_k = 0$$ which would mean that either $$a_{i-1}$$ is zero or $$a_{i}$$ is zero and hence $$k$$ will no longer be the least number such that $$a_k = 0$$. Therefore, to avoid contradiction we have to have $$|a_1| = a_2 - a_1 = a_3 - a_2 = a_4 - a_3 \cdots = |a_{k-1}|$$ If $$-a _1 = a_2 - a_1$$ then $$a_2= 0$$. If $$a_1 = a_2 - a_1$$ then we have $$a_2 = 2a_1$$ $$a_2 - a_1 = a_3 - a_2 \implies a_3 = 3 a_1$$ Similarly, $$a_4 = 4 a_1$$, $$a_5 = 5 a_1$$ and so on. That means, the absolute values of the terms are increasing and hence there is no chance that there will be a $$k$$ such that $$a_k = 0$$ until and unless $$a_1$$ is itself zero.

• Note: Right after the modulus inequality, the OP has started to do case work (Though they haven't mentioned they are) Jul 6, 2021 at 18:24
• This question has been answered in Theorem 2 of this paper arxiv.org/abs/2211.06760. Jul 4, 2023 at 18:29

• You've used $$a \mid b \implies |a| \leq |b|$$ several times, but this is incorrect. The corrected implication is $$a \mid b \implies (|a| \leq |b| \text{ or } b=0).$$ In context, however, this other case relates to the possibility that $$a_i = a_{i+1}$$ for some $$i$$, and you've addressed a similar issue later from $$a_{i-1}=a_{i+1}$$.
• Most of your proof follows the pattern of "Case 1, Case 2, ..., Case k" which can sometimes hide problems for small $$k$$-values. For instance, when $$k=1$$, what does $$|a_1 | \leq |a_2 -a_1 | \leq |a_3 - a_2| \leq \cdots \leq |a_{k-1}| \leq |a_1|$$ even say? And if that sequence of inequalities doesn't exist, can you really argue as you do later? This, of course, can be ignored if you assume, towards a contradiction, that $$k \geq 3$$ at the onset.
• It is incorrect to write $$|a_1| = a_2 - a_1$$ as in $$|a_1| = a_2 - a_1 = a_3 - a_2 = a_4 - a_3 =\cdots = |a_{k-1}|$$ but you never actually use $$|a_1| = a_2-a_1$$ in your proof. Rather, you use the correct $$|a_1| = |a_2-a_1|$$.
• Thanks, I like pedantic reviews. That $k geq 3$ was given in the question so I thought of not making it explicit. Aug 17, 2020 at 7:48
• @Knight As written, the $k$ in the question and your $k$ cannot be the same (this is what you end up proving), so if you want your $k$ to satisfy $k \geq 3$, you actually do need to write that as an assumption. Aug 17, 2020 at 8:06