Library / China Hong Kong Mathematical Olympiad /72 of 89

China Hong Kong Mathematical Olympiad

Algebra Difficulty 6.7 National Olympiad Prove it Hong Kong

Let $f(x) = c_m x^m + c_{m-1} x^{m-1} + \cdots + c_1 x + c_0$ , where each $c_i$ is a nonzero integer. Define a sequence $\{a_n\}$ by $a_1 = 0$ and $a_{n+1} = f(a_n)$ for all positive integers $n$ .

a. Let $i$ and $j$ be positive integers with $i < j$ . Show that $a_{j+1} - a_j$ is a multiple of $a_{i+1} - a_i$ .

b. Show that $a_{2008} \neq 0$ .

Solution

a.
Recall the fact that $b - c \mid f(b) - f(c)$ for any integers $b$ and $c$ . Putting $b = a_{i+1}$ and $c = a_i$ , we immediately obtain
$a_{i+1} - a_i \mid f(a_{i+1}) - f(a_i) = a_{i+2} - a_{i+1}.$
By induction on $j$ , $a_{i+1} - a_i \mid a_{j+1} - a_j$ for any $j > i$ .

b.
Suppose on the contrary that $a_{2008} = 0$ . Note that $a_{2009}-a_{2008} = f(0) = a_2-a_1$ . By part (a), since $a_2 - a_1 \mid a_{k+1} - a_k \mid a_{2009} - a_{2008}$ for $k = 1, 2, \dots, 2007$ , each $a_{k+1} - a_k$ must be $\pm f(0)$ . Now, we have
$0 = a_{2008} - a_1 = \sum_{k=1}^{2007} (a_{k+1} - a_k) = m f(0),$
where $m \in \{-2007, -2005, \dots, -1, 1, 3, \dots, 2007\}$ . This implies $f(0) = 0$ , which contradicts the assumption that $c_0 \neq 0$ . Therefore, $a_{2008} \neq 0$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.