Problem: For each integer $k\geq 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}+\dots + 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}\dotsm a_{n+k} \]
for every integer $n\geq 1$.

Solution: The answer is $a_n$ being an arithmetic progression.
Indeed, if $a_n = d(n-1) + a_1$ for $d \ge 0$ and $n \ge 1$, then
\[ a_{n+1} a_{n+2} \dots a_{n+k} = (a_n+d)(a_n+2d)\dots(a_n+kd) \]
so we can just take $P(x) = (x+d)(x+2d) \dots (x+kd)$.

The converse direction takes a few parts.
\begin{claim*}
  Either $a_1 < a_2 < \dotsb$ or the sequence is constant.
\end{claim*}
\begin{proof}
  Note that
  \begin{align*}
    P(a_{n-1}) &= a_{n}a_{n+1}\dotsm a_{n+k-1} \\
    P(a_n) &= a_{n+1}a_{n+2}\dotsm a_{n+k} \\
    \implies a_{n+k} &= \frac{P(a_n)}{P(a_{n-1})} \cdot a_n.
  \end{align*}
  Now the polynomial $P$ is strictly increasing over $\NN$.

  So assume for contradiction there's an index $n$ such that $a_n < a_{n-1}$.
  Then in fact the above equation shows $a_{n+k} < a_n < a_{n-1}$.
  Then there's an index $\ell \in [n+1,n+k]$ such that
  $a_\ell < a_{\ell-1}$, and also $a_\ell < a_n$.
  Continuing in this way, we can an infinite descending subsequence of $(a_n)$,
  but that's impossible because we assumed integers.

  Hence we have $a_1 \le a_2 \le \dotsb$.
  Now similarly, if $a_n = a_{n-1}$ for any index $n$, then $a_{n+k} = a_n$,
  ergo $a_{n-1} = a_n = a_{n+1} = \dots = a_{n+k}$.
  So the sequence is eventually constant, and then by downwards induction,
  it is fully constant.
\end{proof}

\begin{claim*}
  There exists a constant $C$ (depending only $P$, $k$)
  such that we have $a_{n+1} \leq a_n + C$.
\end{claim*}
\begin{proof}
  Let $C$ be a constant such that $P(x) < x^k + Cx^{k-1}$ for all $x \in \NN$
  (for example $C = c_0 + c_1 + \dots + c_{k-1} + 1$ works).
  We have
  \begin{align*}
    a_{n+k} &= \frac{P(a_n)}{a_{n+1} a_{n+2} \dots a_{n+k-1}} \\
        &< \frac{P(a_n)}{(a_n+1)(a_n+2)\dots(a_n+k-1)} \\
        &< \frac{a_n^k + C \cdot a_n^{k-1}}{(a_n+1)(a_n+2)\dots(a_n+k-1)} \\
        &< a_n + C + 1. \qedhere
  \end{align*}
\end{proof}

Assume henceforth $a_n$ is nonconstant, and hence unbounded.
For each index $n$ and term $a_n$ in the sequence,
consider the associated differences
$d_1 = a_{n+1} - a_n$, $d_2 = a_{n+2} - a_{n+1}$, \dots, $d_k = a_{n+k}-a_{n+k-1}$,
which we denote by
\[ \Delta(n) \coloneq (d_1, \dots, d_k).\]
This $\Delta$ can only take up to $C^k$ different values.
So in particular, some tuple $(d_1, \dots, d_n)$
must appear infinitely often as $\Delta(n)$; for that tuple, we obtain
\[ P(a_N) = (a_N+d_1)(a_N+d_1+d_2) \dots (a_N+d_1+\dots+d_k) \]
for infinitely many $N$.
But because of that, we actually must have
\[ P(X) = (X+d_1)(X+d_1+d_2) \dots (X+d_1+\dots+d_k). \]

However, this \emph{also} means that \emph{exactly} one output to $\Delta$
occurs infinitely often (because that output is determined by $P$).
Consequently, it follows that $\Delta$ is eventually constant.
For this to happen, $a_n$ must eventually coincide with an arithmetic
progression of some common difference $d$,
and $P(X) = (X+d)(X+2d) \dots (X+kd)$.
Finally, this implies by downwards induction that $a_n$ is
an arithmetic progression on all inputs.