numbersandnumbers wrote:

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$

This proof is really nice, I did not see the clever argument for Lemma 3 presented in this solution so I had the following solution:

I have skipped the proof of claims that the $a_i$ get arbitrarily large in the following writeup.

Let $s_1< s_2< \dots$ be an inifinite sequence such that $a_{s_i}\le a_{s_{i+j}}$ for all $j\in \{1,2,\dots k\}$ . Now, $a_{s_i}^{k-1}(a_{s_i}+c_0+c_1+\dots c_{k-1})\prod\limits_{j=1}^k a_{s_{i+j}}\ge a_{s_i}^k$ . Thus, $|a_{s_{i+j}}-a_{s_i}|\le c_0+c_1+\dots c_{k-1}$ . Thus, from each $s_i$ term, consider the polynomial: $P_i(x)=\prod\limits_{i=1}^k (x+a_{s_i+j}-a_{s_i})$ .

By infinite pigeonhole principle, infinitely many of these polynomials are the same. Let's call one such polynomial occuring infinitely many times $S_1(x)$ . Now, for infinitely many values of $x$ , we have $P(x)=S_1(x)$ . Thus, $P(x)=(x+d_1)(x+d_2)\dots (x+d_k)$ for some $d_1, \dots d_k \ge 0$ and infinitely many times we have $a_{s_i}+d_j=a_{s_{i+j}}$ all occuring simultaneously. Let the infinite sequence of $s_i$ with previous property be $t_1<t_2 \dots$ .

Now, $P(a_{t_i+1})=\prod\limits_{j=1}^k P(a_{t_i}+d_1+d_j)$ and thus, $a_{t_i+k+1}=\dfrac{\prod\limits_{j=1}^k P(a_{t_i}+d_1+d_j)}{\prod\limits_{j=1}^k P(a_{t_i}+d_1+d_j)}\cdot a_{t_i+1}$
Thus, again $a_{t_i+k+1}-a_{t_i+1}$ is bounded and we have that polynomials $Q_i(x)=\prod\limits_{j=1}^k(x+a_{t_i+j}-a_{t_i})$ have the same polynomial occuring infinitely many times. Thus, we get a polynomial $S_2(x)$ which occurs infinitely many times of the form $(x+r_1)(x+r_2)\dots (x+r_k)$ but this must be $P(x)$ . Thus, ${d_1,d_2,\dots d_k}-{d_1}={0,d_1,\dots d_k}\setminus {d_t}$ for some $t$ . Thus, the $d_i$ form an AP in some order with common difference $d_1$ . Thus the polynomial is $(x+d)(x+2d)\dots (x+kd)$ .

Now, for each $t_i$ , consider the lowest $l_i$ such that $t_{i+l_i}-t_i\ne l_id$ . If such $l_i$ exist infinitely often then amongst each of these, we again have that $|t_{i+l_i}-t_{i+l_i+j}|$ is bounded for $j\in \{1,2,\dots k\}$ . Thus repeating our previous argument, we get that $t_{i+l_i+j}-t_{l_i} > 0$ for all $j$ but $t_{i+l_i}-t_i\ne l_i d$ , thus we get that for some $j>l_i$ , we have $t_{i+j}-t_{i+l_i} =l_id$ which implies $t_{i+j} \le t_{l_i+j}$ which is a contradiction.

Thus, such $l_i$ do not exist infinitely often. Thus, there is a term $t_i$ such that $a_{t_i+j}-a_{t_i}=jd$ for all $j\in {1,2,\dots k}$ and polynomial is $(x+d)(x+2d)\dots (x+kd)$ and using this we can induct on the sequence in both directions to find that if forms the required AP with common difference $d$ . Thus, we are done!

I really liked the problem and don't really have much more to remark which is different from the previous comments. I do believe that it's on an easier side of P3s but that does not make it inappropriate for the position. The best way to judge is to just wait for the statistics to come out