Is there a way to guarantee that the sequence will eventually reach 0?

[Ackbach]

Here is this week's POTW:

-----

Let $f(x)$ be a polynomial with integer coefficients. Define a sequence $a_0,a_1,\ldots$ of integers such that $a_0=0$ and $a_{n+1}=f(a_n)$ for all $n\geq 0$. Prove that if there exists a positive integer $m$ for which $a_m=0$ then either $a_1=0$ or $a_2=0$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 264 - May 23, 2017

This was Problem A-6 in the 2000 William Lowell Putnam Mathematical Competition.

Congratulations to Kiwi for his correct solution, which follows:

Spoiler

Let \(f(x)=\sum^r_0 b_ix^i.\)

Then
\(a_0=0\), \(a_1=f(a_0)=f(0)=b_0\), \(a_2=f(b_0)\)

Now if \(a_m=0\) then \(f(a_{m-1})=0\) and \(a_{m-1}\) is a root of f(x). Therefore

\((x-a_{m-1})\) divides \(\sum^r_0 b_ix^i,\) from which we can see that \(a_{m-1}\) divides \(b_0\) as they are all integers.

Case 1; \(b_0 = 0\)
\(a_1=f(a_0)=f(0)=b_0=0\) and we are done.

Case 2; \(b_0 \neq 0\)
Now \(b_0\) divides \(a_1\) because they are equal. Assume as an inductive hypothesis that \(b_0\) divides all \(a_i\) then
\(a_{n+1}=f(a_n)= \sum^r_1 b_i(a_n)^i+b_0\) which is divisible by \(b_0\). So by induction \(b_0\) divides all \(a_i\).

So \(b_0\) divides \(a_{m-1}\) and \(a_{m-1}\) divides \(b_0;\) therefore \(a_{m-1}=b_0\) and therefore

\(a_2=f(a_1)=f(b_0)=f(a_{m-1})=a_m=0.\)