2
$\begingroup$

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.

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

1 Answer 1

4
$\begingroup$

There are some concerning steps, but nothing is particularly difficult to address.

  • 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|$.
$\endgroup$
2
  • $\begingroup$ Thanks, I like pedantic reviews. That $k geq 3$ was given in the question so I thought of not making it explicit. $\endgroup$ Aug 17, 2020 at 7:48
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 17, 2020 at 8:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .