IMO 2023 | PROBLEM 3 - SOLUTION - 8 July 2023

Problem 3.
For each integer $k\geqslant 2,$ determine all infinite sequences of positive integers $a_1,a_2,\dots$ for which there exists a polynomial $P$ of the form $P(x)=x^k+c_{k-1}x^{k-1}+\cdots c_1 x+c_0,$ where $c_0,c_1,\dots,c_{k-1}$ are non-negative integers, such that
$P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$
for every integer $n\geqslant 1.$

proposed by Ivan Chan, Malaysia

Solution

The answer is all constant or ascending arithmetic sequences, i.e. $a_n = b + (n-1)d$ for positive integers $b$ and nonnegative integers $d$ . These work since we can take $P(x) = (x + d)(x + 2d) \cdots (x + kd)$ . Now we show that no others work.

Before we begin, we note that given $P$ and $k$ consecutive values $a_{n}, \ldots, a_{n+k-1}$ of the sequence, the rest of the sequence can be fully determined, since we have
$a_{n+k} = \frac{P(a_n)}{a_{n+1}\cdots a_{n+k-1}}$
and for $n > 1$ , $a_{n-1} = P^{-1}(a_n\cdots a_{n+k-1})$ (note that $P$ is increasing and hence injective on the positive integers). Call these two relations $(\star)$ .

First, let's handle the special case $P(x) = x^k$ ; we aim to prove that the $a_n$ are constant. To see this, let $b$ be the minimum value attained by any $a_n$ . Then, if $a_n = b$ , we have that $a_{n+1} \cdots a_{n+k} = b^k$ but $a_{n+i} \geq b$ for all $i$ ; therefore $a_{n+1} = b$ . Therefore the sequence is eventually constant at $b$ ; by applying $(\star)$ we get that $a_n = b$ for all $n$ , as desired.

Now assume that some non-leading coefficient of $P(x)$ is positive. We prove a bunch of lemmas.

Lemma 1. The sequence $(a_n)$ achieves arbitrarily large values.
Proof. Since $P(x) > x^k$ for all positive integers $x$ , we conclude that $\max\{a_{n+1},\ldots,a_{n+k}\} > a_n$ for all $n$ . Iterating this proves the claim. $\blacksquare$

Lemma 2. For every $m$ , there are only finitely many $n$ with $a_n = m$ .
Proof. For every such $n$ , we must have $a_{n+1},\ldots,a_{n+k} \leq P(m)$ . Thus, if there are infinitely such $n$ , we can find some $n < n'$ with $a_{n+i} = a_{n'+i}$ for all $1 \leq i \leq k$ . By iterating $(\star)$ we get that $a_n$ is periodic, which contradicts Lemma 1. $\blacksquare$

Lemma 3. $a_{n+1} \geq a_n$ for all $n$ .
Proof. Suppose not. Let $m$ be the minimum value such that there exists an $n$ such that $a_n > a_{n+1} = m$ . But then,
$1 > \frac{P(a_{n+1})}{P(a_n)} = \frac{a_{n+k+1}}{a_{n+1}},$
so $a_{n+k+1} < a_{n+1}$ . Thus, if we let $m' = \min \{a_{n+2},\ldots,a_{n+k+1}\}$ , which must be less than $m$ , and $n'$ be the minimal $n+2 \leq n' \leq n+k+1$ with $a_{n'} = m'$ , we find that $a_{n'-1} > a_{n'} = m'$ , contradicting the minimality of $m$ . $\blacksquare$

Lemma 4. $a_{n+1} - a_n = O(1)$
Proof. By Lemma 3, $a_{n+1}^k \leq a_{n+1} \cdots a_{n+k} = P(a_n)$ , so $a_{n+1} - a_n \leq P(a_n)^{1/k} - a_n$ . But this is bounded above. $\blacksquare$

By Lemma 4, there are now finitely many possibilities for the tuple $(a_{n+1} - a_n, a_{n+2}-a_n,\ldots,a_{n+k+1} - a_n)$ , so there must be one, call it $(d_1,\ldots,d_{k+1})$ , which appears infinitely many times. Then we must have
$P(a_n) = (a_n + d_1) \cdots (a_n + d_k) \text{ and } P(a_n+d_1) = (a_n+d_2)\cdots (a_n + d_{k+1})$ for infinitely many $n$ . By Lemma 2, this means that
$P(x) = (x + d_1) \cdots (x + d_k) \text{ and } P(x+d_1) = (x+d_2)\cdots (x + d_{k+1})$ for infinitely many $x$ , meaning that the relations above have to hold as polynomials. Now, by Lemma 3 we have $d_1 \leq \cdots \leq d_{k+1}$ . Moreover, since a polynomial can be factored into linear factors in only one way, we conclude that $d_i = d_{i+1} - d_i$ for all $1 \leq i \leq k$ , i.e. $d_i = id_1$ for all $i$ . As a result, $P(x) = (x + d_1)\cdots(x + kd_1)$ , and there exists an $n$ with $a_{n+i} = a_n + id_1$ for all $0 \leq i \leq k+1$ . By iterating $(\star)$ forwards, we get that there exists an integer $b$ with $a_n = b + (n-1)d_1$ for all large $n$ . If $b > 0$ , we can iterate $(\star)$ backwards and conclude. Otherwise, we can iterate $(\star)$ backwards to get some $n > 1$ with $a_n \leq d_1$ . But then $a_n \cdots a_{n+k-1} < P(1)$ , so there is no possibility for $a_{n-1}$ . So we are done in this case as well. $\square$