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$