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.$

My proposal :>

I think that this problem can be rephrased as a recurrence sequence, with: $a_{n+k}=\frac{P(a_n)}{a_{n+1}...a_{n+k-1}}$ So now you only need to find ALL $P(x),a_1,a_2,...,a_{k}$ so that every following terms are integers (And even worse, this is very tedious) However, there is a weakness: You can prove by induction that: $a_x=\frac{a_{x-k}P(a_{x-k})}{P(a_{x-k-1}}$

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$

I'm not sure! Even I don't know, I'm just guessing that the proposer of this problem is Mr. Safaei from Iran. Does anyone know the proposer?

I am the proposer [Ivan Chan from Malaysia]

Congrats. it's a nice problem! Thanks for telling that!

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$ elegant solution sir though I think this problem was kinda easy for imo#3. it's more like a hard #2 or #5

Huh. This is actually surprisingly amazing of a problem and I'm honestly in love . Main Claim. The sequence $a_n$ is increasing. Suppose $a_n$ is a minimum of the sequence (which is possible as this is an integral sequence). If $a_n<a_{n-1}$ and $n>1$, \[a_{n+k}P(a_{n-1})=\prod_{i=n-1}^ka_i=a_nP(a_n)<a_nP(a_{n-1})\]as $P$ is monotonic, so $a_{n+k}<a_n$. This is clearly impossible, so thus for any minimum, all previous terms must be equal. In particular, the sequence $a_n$ is (not necessarily strictly) increasing. $\blacksquare$ To finish, simply note that there exists some $y$ such that $P(x)<(x+y)^k$; for example, \[y>\text{max}\left(\frac{c_j}{\binom kj}\right)\]This implies that since $a_n\leq a_{n+1}<a_n+y$, we have \[(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})\in [0,y]^{k+1}\]by the Pigeonhole Principle, some value $(a'_1,\ldots,a'_{k+1})$ appears infinitely often. Call $n$ good if $(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})=(a'_1,\ldots,a'_{k+1})$. Then, \[P(x)=\prod_{j=1}^k\left(x+\sum_{i=1}^ja'_i\right)=\prod_{j=1}^k\left(x+\sum_{i=2}^{j+1}a'_i\right)\]for infinitely many values of $x$ (which comes from taking $x=a_n,a_{n+1}$ where $n$ is good), so thus these factors must be equal up to permutation. However, as $a'_i\geq 0$, we know $a'_i=a'_{i+1}$, so $a'_i$ is constant. This means that $a_i$ is an arithmetic sequence, and clearly it is a non-decreasing one.

Uh, finally solved this problem. Since my solution is quite the same as #5, I'll just leave some thoughts here. First, this was very fun to solve tho. Even though the solution is fairly short, it's not easy to find. I enjoyed this problem a lot, so I think this is a very appropriate P3 problem. Just wished this was a little harder

naman12 wrote: Huh. This is actually surprisingly amazing of a problem and I'm honestly in love . Main Claim. The sequence $a_n$ is increasing. Suppose $a_n$ is a minimum of the sequence (which is possible as this is an integral sequence). If $a_n<a_{n-1}$ and $n>1$, \[a_{n+k}P(a_{n-1})=\prod_{i=n-1}^ka_i=a_nP(a_n)<a_nP(a_{n-1})\]as $P$ is monotonic, so $a_{n+k}<a_n$. This is clearly impossible, so thus for any minimum, all previous terms must be equal. In particular, the sequence $a_n$ is (not necessarily strictly) increasing. $\blacksquare$ To finish, simply note that there exists some $y$ such that $P(x)<(x+y)^k$; for example, \[y>\text{max}\left(\frac{c_j}{\binom kj}\right)\]This implies that since $a_n\leq a_{n+1}<a_n+y$, we have \[(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})\in [0,y]^{k+1}\]by the Pigeonhole Principle, some value $(a'_1,\ldots,a'_{k+1})$ appears infinitely often. Call $n$ good if $(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})=(a'_1,\ldots,a'_{k+1})$. Then, \[P(x)=\prod_{j=1}^k\left(x+\sum_{i=1}^ja'_i\right)=\prod_{j=1}^k\left(x+\sum_{i=2}^{j+1}a'_i\right)\]for infinitely many values of $x$ (which comes from taking $x=a_n,a_{n+1}$ where $n$ is good), so thus these factors must be equal up to permutation. However, as $a'_i\geq 0$, we know $a'_i=a'_{i+1}$, so $a'_i$ is constant. This means that $a_i$ is an arithmetic sequence, and clearly it is a non-decreasing one.

I really love your remarks there: its pretty much what I felt when I solved the problem - the properties are rather surprising for me as well!

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

Claim 1: $A$ is either unbounded or constant.

Claim 2: $A$ is nondecreasing

So if $A$ is not constant we get that at some point all numbers after some $a_N$ are $a_N+O(1)$. Now if we have that set of $a_{N+k}-a_N$ is not always the same after some point we get that there are at least two of such sets appearing infinitely many times, call them $S$ and $S'$, so $P(x)=\Pi_{p\in S}(x+p)=\Pi_{q\in S'}(x+q)$, contradiction, so that set is fixed after some arbitrarily big $a_N$. Claim: This set is an arithmetic progression

Now we know that $A$ is an arithmetic progression after some point so $P(x)=\Pi_{i=1}^{i=k} (x+ti)$. Now we can just go backwards and get that $A$ was an arithmetic progression all along.

navi_09220114 wrote: It all started with a desperate need for NT problems in our country's TST lol. My friend Anzo gave me a bootleg of 2015 A1: "Let $a_0$ be arbitrary postive real, $a_{n + 1} = \frac{(n + 2)a_n}{(a_n^2 + n + 1)}$. Determine $\lim_{n \rightarrow \infty} (a_1 + ... + a_n) - n$ in terms of $a_0$." OMG I'm so honored to be featured by the proposer himself It is a very beautiful problem, and no, I haven't solved it yet. One more thing to add into my bucket list! navi_09220114 wrote: Meanwhile, the NT we used for the TST is here lol: (It's simple but nice so do try it!) "Do there exist infinitely many triples of positive integers $(a, b, c)$ such that $a$, $b$, $c$ are pairwise coprime, and $a! + b! + c!$ is divisible by $a^2 + b^2 + c^2$?" This was Malaysian TST P4 this year, and it's mine. (Could have been a borderline P5 tbh).

Nice problem with infinite descent method. The answer is all non-decreasing arithmetic sequences, i.e. $a_n=b+(n-1)d$ for a positive integer $b$ and a nonnegative integer $d$. Clearly those work since we can choose $$P(x)=\prod_{i=1}^k(x+id).$$ The main claim is as follows. Claim 1. $a_n\le a_{n+1}$ for all positive integers $n$. Proof. Suppose not. Pick positive integers $m,n$ such that $a_n>a_{n+1}=m$ and $m$ is minimal. As $c_{k-1},\ldots,c_0$ are all nonnegative, the polynomial $P(x)$ is strictly increasing over positive integers so $$1>\frac{P(a_{n+1})}{P(a_n)}=\frac{a_{n+k+1}}{a_{n+1}}.$$It follows that $m=a_{n+1}>a_{n+k+1}$. Let $n'\in[n+1,n+k]$ is the maximal integer such that $a_{n'}\ge m$ and let $m'=a_{n'+1}$. then $m'<m$ and $a_{n'}>a_{n'+1}=m'$, contradiction to the minimality of $m$. $\square$ Now we divide into cases. Case 1. The sequence $\{a_n\}$ is bounded. Since $\{a_n\}$ is weakly increasing, then it is eventually constant, so there exists $t,c\in\mathbb N$ such that $a_n=c$ for all $n\ge t$. Then we have $$c^k\le P(c)=P(a_t)=\prod_{i=1}^k P(a_{t+i})=c^k.$$Since equality holds we have $c_{k-1}=\dots=c_0=0$ so $P(x)=x^k$. From backwards induction it follows that $P(t-j)=c$ for all $1\le j\le t-1$. Hence $\{a_n\}_{n\in\mathbb N}$ is constant. Case 2. $\{a_n\}$ is unbounded. Let $c\doteqdot\sum_{i=0}^{k-1}c_i$. Observe that for every positive integer $n$ we have $$P(n)\le n^k+cn^{k-1}=(n+c)n^{k-1}$$Thus, for every positive integer $n$, $$(a_n+c)a_n^{k-1}\ge P(a_n)=\prod_{i=1}^ka_{n+i}\ge a_{n+k}a_n^{k-1}.$$Hence $a_{n+k}\le a_n+c$. Claim 2. Let $e_1,e_2,\ldots,e_k$ be nonnegative integers such that there exist infinitely positive integers $n$ for which $a_{n+i}-a_n=e_i$ for all integer $i\in[1,n]$. Then $P(x)=\prod_{i=1}^n (x+e_i)$. Proof. By assumption, there exists an infinite subset $X\subset\mathbb N$ such that $$(a_{n+1}-a_n,a_{n+2}-a_n,\ldots,a_{n+k}-a_n)=(e_1,\ldots,e_k)$$for every $n\in X$. Then for every $n\in X$ we have $$P(a_n)=\prod_{i=1}^k a_{n+i}=\prod_{i=1}^k (a_n+e_i).$$Hence the equation $P(x)=\prod_{i=1}^n (x+e_i)$ has a solution set $\{a_n\mid n\in X\}$. Moreover, as $\{a_n\}_{n\in\mathbb N}$ is nondecreasing and unbounded, the set $\{a_n\mid n\in X\}$ is unbounded as well, so $P(x)=\prod_{i=1}^n (x+e_i)$ in $\mathbb Z[x]$. $\square$ Claim 3. Let $d$ be a nonnegative integer such that there exist infinitely many positive integers $n$ for which $a_{n+1}-a_n=d$. Then $d$ is the smallest nonnegative integer such that $P(-d)=0$. Proof. By assumption, there exists an infinite subset $X\subset\mathbb N$ such that $a_{n+1}-a_n=d$ for every $n\in X$. Define a function $f\colon X\to\mathbb Z_{\ge 0}^k$ by $$f(n)\doteqdot (a_{n+1}-a_n,a_{n+2}-a_n,\ldots,a_{n+k}-a_n).$$As $a_{n+i}-a_n\le c$ for all $n\in X$ and $i\in[1,k]$, the image of $f$ is finite. Hence by pigeonhole, there exists an infinite subset $Y\subset X$ and nonnegative integers $e_1,e_2,\ldots,e_k$ such that $f(n)=(e_1,\ldots,e_k)$ for every $n\in Y$. By claim 2 we have $P(x)=\prod_{i=1}^n (x+e_i)$. As $d=e_1\le e_2\ldots\le e_k$, the number $d$ is the smallest with property $P(-d)=0$. $\square$ Now define $d_n\doteqdot a_{n+1}-a_n$ for each positive integer $n$. As $0\le d_n\le c$, the sequence $\{d_n\}_{n\in\mathbb N}$ is bounded, so there exists a nonnegative integer $d$ which occurs infinitely many in $\{d_n\}_{n\in\mathbb N}$. By claim 3, $d$ is unique so by boundness again, the sequence $\{d_n\}_{n\in\mathbb N}$ is eventually constant with value $d$. Formally, there exists a positive integer $m$ such that $d_n=d$ for all $n\ge m$. Pick such a minimal $m$. If $m=1$ then we are done, so assume $m\ge 2$ for contrary. Claim 2 implies that $P(x)=\prod_{i=1}^k(x+id)$. Let $Q(x)\doteqdot \prod_{i=1}^k(x+(i-1)d)$, hence $P(x)=Q(x+d)$. By hypothesis we have $$Q(a_{m-1}+d)=P(a_{m-1})=\prod_{i=1}^k a_{m-1+i}=\prod_{i=1}^k(a_m+(i-1)d)=Q(a_m).$$As the polynomial $Q(x)$ is strictly increasing over positive integers, we have $a_{m-1}+d=a_m$ or $d_{m-1}=d$, contradiction. To summarize, in both cases we have proved that $a_1,a_2,\ldots$ is an arithmetic nondecreasing sequence, hence we are done.

Nice problem, on the easier side of a P3 maybe. Note that $P$ is strictly increasing, and there exists a positive integer $M>0$ such that $x^k \leq P(x) \leq (x+M)^k$ for all $x \geq 0$. Claim 1: $a_1,a_2, \dots$ is non-decreasing. Proof: Assume FTSOC that $a_n>a_{n+1}$ for some $n$. Choose the smallest index $m \geq n$ such that $a_m = \min \{a_n,a_{n+1}, \dots\}$. Clearly $m \geq n+1$, and $a_{m-1}>a_m$. But then $$P(a_{m-1})=a_m \cdots a_{m+k-1}>P(a_m)=a_{m+1} \cdots a_{m+k}$$which gives $a_m>a_{m+k}$, contradicting minimality of $a_m$. $\blacksquare$ Claim 2: If $a_n=a_{n+1}$ for some $n$, then the sequence is constant. Proof: $a_n=a_{n+1}$ $\implies$ $P(a_n)=P(a_{n+1})$ $\implies$ $a_{n+1}=a_{n+k+1}$, which by non-decreasing gives $a_n=a_{n+1}=a_{n+2}=\cdots=a_{n+k+1}$. Now an easy induction in both directions gives us that $a_i$ is constant. $\blacksquare$ From now on, we assume $a_1,a_2, \dots$ is strictly increasing. Now, $a_{n+1}^k<P(a_n)\leq (a_n+M)^k$ $\implies$ $a_{n+1} \leq a_n+M$ for all $n$. Therefore the differences $a_{n+1}-a_n,a_{n+2}-a_n, \dots a_{n+k}-a_n$ form a $k$-element subset of $\{1,2, \dots kM\}$, and so by pigeonhole principle, some subset $i_1<i_2<\cdots <i_k$ is achieved infinitely often: i.e., $P(a_n)=(a_n+i_1)(a_n+i_2)\cdots (a_n+i_k)$ for infinitely many $n$. Since the sequence is strictly increasing, we must in fact have $P(x)=(x+i_1)(x+i_2)\cdots(x+i_k)$. Claim 3: $i_l=li_1$ for all $1\leq l \leq k$. Proof: We use induction on $l$. Base case $l=1$ is trivial. Assume we have proved the claim up till $l-1$. For all such $n$ for which the differences are $i_1<i_2<\cdots i_k$, we have $$P(a_n+i_1)=P(a_{n+1})=a_{n+2}\cdots a_{n+k+1}=(a_n+i_2)\cdots(a_n+i_k)a_{n+k+1}$$So $a_n+i_l \mid P(a_n+i_1)$ for all such (infinitely many) $n$. Again since the sequence is strictly increasing, we must in fact have $x+i_l \mid P(x+i_1)$ as polynomials $\implies$ $i_l=i_1+i_p$ for some $p \leq k$. If $p \leq l-2$, by induction hypothesis $i_1+i_p=i_{p+1}<i_l$, and if $p \geq l$, we have $i_1+i_p > i_p \geq i_l$. Therefore the only possibility is $p=l-1$, and so by induction hypothesis, $i_l=i_1+i_{l-1}=li_1$, as required. Thus we are done by induction. $\blacksquare$ Write $i_1=d$, and again choose an $n$ so that the differences are $d,2d,\dots ,kd$. Now, $$(a_n+2d)(a_n+3d)\cdots(a_n+(k+1)d)=P(a_{n+1})=(a_n+2d)\cdots(a_n+kd)a_{n+k+1}$$which gives $a_{n+k+1}=a_n+(k+1)d$ as well, so an easy induction gives $a_n,a_{n+1}, \dots$ is an AP with common difference $d$. Now for the reverse part: $$(a_{n-1}+d)\cdots(a_{n-1}+kd)=P(a_{n-1})=a_n(a_n+d)\cdots(a_n+(k-1)d)=P(a_n-d)$$which gives $a_{n-1}=a_n-d$, and now an easy induction gives that in fact the entire sequence is an AP. For an AP with common difference $d \geq 0$, clearly the polynomial $P(x)=(x+d)(x+2d)\cdots(x+kd)$ works, so the answer is $\boxed{\text{all non-decreasing arithmetic progressions.}}$

Very nice NT! All such sequences are positive arithmetic sequences with natural common difference. If $P(x)=x^k$, then $a_n^k=a_{n+1}a_{n+2}...a_{n+k}$. Pick $a_m=$minimum of $\{a_i\}$ and $a_m^k=a_{m+1}a_{m+2}...a_{m+k} \ge a_m^k$, so $a_m=a_{m+1}=a_{m+2}=...=a_{m+k}$, so $\{a_i\}$ is constant sequence. If else, we first prove that $\{a_i\}$ is nondecreasing. For positive number $n$, define $f(n)$ to be the label of the first smallest term in $a_m, a_{n+1}, a_{n+2}, ...$, then $P\left(a_f(n)\right)=a_{f(n)+1} a_{f(n)+2} \cdots a_{f(n)+k}$ and $P\left(a_f(n)-1\right)=a_{f(n)} a_{f(n)+1} \cdots a_{f(n)+k-1}$, so $\frac{P\left(a_{f(n)}\right)}{P\left(a_{f(n)-1}\right)}=\frac{a_{f(n)+k}}{a_{f(n)}} \ge 1$. Since $P$ is strictly increasing, $a_{f(n)} \ge a_{f(n)-1}$, so $f(n)=n$, thus $\{a_i\}$ is nondecreasing. From this we can get $\{a_i\}$ is unbounded. Let $d_n=a_n-a_{n-1} \ge 0$. $P(a_n)=\prod_{i=1}^k a_{n+i}=\prod_{i=1}^k (a_n+d_{n+1}+d_{n+2}+...+d_{n+i}) (*)$ When ${n}$ is sufficiently large than $a_n$ is also sufficiently large, $c_{k-1} \ge (d_{n+1})+(d_{n+1}+d_{n+2})+...+(d_{n+1}+d_{n+2}+...+d_{n+k})$, so for every large ${n}$, $d_n$ is finite, so the number of pairs $(d_{n+1}, d_{n+1}+d_{n+2}, ..., d_{n+1}+d_{n+2}+...+d_{n+k})$ is also finite. So there are at least one pair $(d_{n+1}, d_{n+1}+d_{n+2}, ..., d_{n+1}+d_{n+2}+...+d_{n+k})$ that has infinite numbers of corresponding $a_n$. Note that $(*)$ is a polynomial of $a_n$, so $P(x)=\prod_{i=1}^k (x+d_{n+1}+d_{n+2}+...+d_{n+i})$ is true for any real ${x}$. This implies that since $P(x)$ is fixed, pair $(d_{n+1}, d_{n+1}+d_{n+2}, ..., d_{n+1}+d_{n+2}+...+d_{n+k})$ is the only pair for any sufficiently large $n$ (since they are just the opposite numbers of roots of $P$ and they are in nondecreasing order, so there can't be two such pairs), which means that the pair $(d_{n+1}, d_{n+1}+d_{n+2}, ..., d_{n+1}+d_{n+2}+...+d_{n+k})$ keeps the same for any large ${n}$, so $d_{n+1}=d_{n+2}$, which is $a_{n+2}-a_{n+1}=a_{n+1}-a_{n}=d$ is true for any large ${n}$ and $P(x)=(x+d)(x+2d)(x+3d)...(x+kd)$. Plugging back and we can get $a_{n+1}-a_{n}=d$ is true for any positive number ${n}$. Done!

Very nice problem! Probably on the easier side of P3s, but still appropriate. I got it quite quick, but the techniques seem rather sophisticated. I would say maybe MOHS 35

Let us denote $\delta_r (a_j):=a_{j+r}-a_j.$ There exists a set $J$ of infinitely many $j$'s for which $a_j\le a_{j+r},r=1,2,\dots,k$ for each $j\in J.$ We have $$P(a_j)=(a_j+\delta_1(a_j))(a_j+\delta_2 (a_j))\cdots (a_j+\delta_k (a_j)).\qquad (1)$$Consider the $k$ tuple $$t(a_j):= \big(\delta_1 (a_j), \delta_2 (a_j),\dots, \delta_k (a_j)\big)$$where $j$ runs through $J.$ It can be seen that the pattern $t(a_j)$ must take infinitely many times the same value say $(\delta_1,\delta_2,\dots,\delta_k)$ (since $\delta_i (a_j)$ should be bounded). Consider now the polynomial $$Q(x):= (x+\delta_1)(x+\delta_2)\cdots (x+\delta_k ).\qquad (2)$$According to $(1),$ we have $P(a_j)=Q(a_j)$ for infinitely many indices $j\in J'.$ In case the set $\{a_j : j\in J'\}$ is infinite we get $P(x)\equiv Q(x).$ If we assume that this set is finite, it easily follows $(a_n)$ is periodic. Taking a maximal $a_j$ and using that $c_i\ge 0,i=1,2,\dots,k-1$ and $(2),$ we get that in this case $(a_n)$ is constant. It remains to consider only the case $$P(x)=(x+\delta_1)(x+\delta_2)\cdots (x+\delta_k )$$where $\delta_i\ge 0.$ It easily follows that $\delta_i, i=1,2,\dots,k$ must be an arithmetic progression, i.e., $$P(x)=(x+a)(x+2a)\cdots (x+ka )\,,\, a\in \mathbb{Z}_{\ge 0}.$$In this case $a_n=a_0+ (n-1)a, n=1,2,\dots; a_0\in\mathbb{Z}.$

We claim the answer is all arithmetic progressions with common difference nonnegative. These easily work by using the polynomial $P(x) = (x + D)(x + 2D) \cdots (x + k D)$, where $D$ is the common difference of the arithmetic sequence. Now we prove they are the only solutions. Assume that $(a_i)$ is not an arithmetic progression henceforth. Claim: $(a_i)$ is unbounded. Proof: Suppose not, and it was bounded above by a constant $M$. We see that $P(x) \ge x^k$ for any $x$, so choosing $a_n = M$, we get that $a_{n+1} a_{n+2} \cdots a_{n+k} \ge M^k$, so $a_{n+1} = a_{n+2} \cdots = a_{n+k} = M$, and thus $P(a_n) = a_n^k$, so all the $c_i$ must be $0$, so $P(x) = x^k$. Then, $a_{n-1}^k = M^k$, so $a_{n-1} = M$. Therefore $a_n = M$ implies that $a_{n-1} = M$ and $a_{n+1} = M$. Inducting upwards and downwards gives $(a_i)$ is constant, contradiction. $\square$ Claim: $(a_i)$ is nondecreasing Proof: Suppose $a_n > a_{n+1}$ for some $n$ and take $n$ to be the smallest in which this happens. Let $a_m$ be the smallest element of the sequence after $a_n$ and choose $m$ such that $a_m \ne a_{m-1}$. Then, $P(a_{m-1}) > P(a_m)$, so $a_m > a_{m + k}$, contradiction to the minimality of $a_m$. $\square$ Claim: The sequence $b_i = a_{i+1} - a_i$ is bounded above. Proof: Suppose it could hit arbitrarily large values. Then\[P(a_n) = (a_n + b_n)(a_n + b_n + b_{n+1})\cdots (a_n + b_n + b_{n+1} + \cdots + b_{n + k - 1}) \]Now we know that there exists $N$ such that $P(x) < (x + N)^k$ (selecting $N$ way bigger than any of the $c_i$ fits), so choosing $b_n$ such that $b_n > N$ gives a contradiction. $\square$ Now we note by pigeonhole that there exists some $(b_n, b_{n+1}, \ldots, b_{n + k - 1})$ tuple that occurs for infinitely many $n$. Call the tuple $(x_1, x_2, \ldots, x_k)$. We get that\[P(x) = (x + x_1)(x + x_1 + x_2) \cdots (x + x_1 + x_2 + \cdots + x_k) \]Claim: For all sufficiently large $m$, we have $(b_m, b_{m+1},\ldots, b_{m + k - 1}) = (x_1, x_2, \ldots, x_k)$. Proof: Suppose not. Then there are infinitely many $m$ such that $(b_m, b_{m+1}, \ldots, b_{m +k - 1})$ is not equal to $(x_1, x_2, \ldots, x_k)$, so there exists some other $(y_1, y_2, \ldots, y_k)$ equal to $(b_m, b_{m+1}, \ldots, b_{m +k - 1})$ for infinitely many $m$. However, we get that\[P(x) = (x + y_1)(x + y_1 + y_2) \cdots (x + y_1 + y_2 + \cdots + y_k)\]The smallest term in this expression is $x + y_1$, while the smallest term in the other expression for $P(x)$ is $x + x_1$, but those are different, so they cannot be the same polynomial, absurd. $\square$ Since this is the case for all sufficiently large $m$, we get that $b_m = x_1$ for all sufficiently large $m$, hence $x_1 = x_2 = \cdots = x_k = D$, so\[P(x) = (x + D)(x + 2D) \cdots (x + kD)\]Claim: $b_m = D$ for all positive integers $m$. Proof: Suppose not, and let $t$ be the largest positive integer such that $b_t\ne D$. We have\[P(a_t) = (a_t + b_t)(a_t + b_t + D) \cdots (a_t + b_t + D(k-1)) \]If $b_t > D$, then\[P(a_t) = (a_t + b_t)(a_t + b_t + D) \cdots (a_t + b_t + D(k-1)) > (a_t + D)(a_t + 2D) + \cdots (a_t + kD) = P(a_t)\]If $b_t < D$, then\[P(a_t) = (a_t + b_t)(a_t + b_t + D) \cdots (a_t + b_t + D(k-1)) < (a_t + D)(a_t + 2D) + \cdots (a_t + kD) = P(a_t)\]Both of these are absurd, so $b_t = D$, contradiction. $\square$ Therefore $a_{i+1} - a_i = D$ for all $i$, which means $(a_i)$ is an arithmetic sequence, as desired. Due to $(a_i)$ being nondecreasing, the common difference of the arithmetic sequence is nonnegative.

Here is a rather long solution with ewan. We somehow missed that you could show nondecreasing without too much effort and thus found the problem to be much harder than a normal olympiad problem. I'll write up the proof as a series of lemmas. Lemma 0: All nondecreasing arithmetic sequences work, and if $a_1, a_2, \ldots$ works and is bounded, then it is constant. Proof omitted; this part is just bookwork. Now, fix an unbounded working sequence $a_1, \ldots$ and corresponding polynomial $P$. In addition, let $Q(x) = xP(x)$. Note that $P, Q$ are both increasing and that $P(x), Q(x) \geq x$ for $x \geq 1$. Note that \[ a_i \leq P(a_i) = a_{i+1}(a_{I+2} \cdots a_{i+k}) \leq a_{I+1}P(a_{i+1}) = Q(a_{i+1}). \]Iterating yields $a_i \leq Q^t(a_{i+t})$. Furthermore, note that there exists some fixed positive integer $D$ such that $P(x) \leq (x+D)^k$ for all $x\geq 0$. Lemma 1: In fact, $\lim\limits_{n\to \infty} a_n = \infty$.

Lemma 2: There exists a universal constant $C$ (depending on $a_i$ and $P$) such that $a_n \leq Cn$ always.

Lemma 3: There exists some constant $L$ (again dependent on $P$ and $a_i$) such that for sufficiently large $i, j$ with $1 \leq j -i \leq k$, $|a_j - a_i|$ is either at most $L$ or $\Omega(a_j^{1/k})$.

Now we are ready for the key claim: Lemma 4: In fact, $a_{i+1}-a_i$ is bounded from above.

Now we are nearly done, and the rest is similar to everyone else, except that we managed to use asymptotic-type arguments here as well instead of infinite pigeonhole. Lemma 5: $a_{i+1} - a_i$ is also bounded from below.

Lemma 6: For sufficiently large $n$, we have \[ a_{n+1} + \cdots + a_{n+k} - ka_n = c_{k-1}. \]

Lemma 7: $a_{n+1} - a_n$ is eventually constant.

Suppose that $d = a_{n+1} - a_n = a_{n+2} - a_{n+1} = \cdots > 0$. Then, since $P(x) = (x+d)\cdots (x+kd)$ for $x = a_n, a_{n+1}, \ldots$, we must have $P(x) = (x+d) \cdots (x+kd)$ in general. It follows from backwards induction that: \begin{align*} P(a_{n-1}) = (a_{n-1} + d) \cdots (a_{n-1} + kd) &= a_n \cdots a_{n+k-1} \implies a_{n-1} = a_n - d \\ P(a_{n-2}) = (a_{n-2} + d) \cdots (a_{n-2} + kd) &= a_{n-1} \cdots a_{n+k-2} \implies a_{n-2} = a_{n-1} - d \\ &\vdots \\ P(a_1) = (a_1 + d) \cdots (a_1 + kd) &= a_2 \cdots a_{k+1} \implies a_1 = a_2 - d, \end{align*}which implies that $a_1, a_2, \ldots$ is an arithmetic sequence, completing the proof.

Main Claim) $a_1$ must be the minimum value of sequence $a$ pf) There obviously must exist a minimum value of sequence $a$, as the sequence is restricted to positive integers. Assume $a_1$ is not the minimum. In other words, there exists $a_i$ ($i \neq 1$) such that $a_i$ is the minimum of $a$. Let $a_i$ be the first of such minimum values. Then, we can safely say that $a_{i-1} > a_i$. We know that $P(a_{i-1}) = a_i a_{i+1} \ldots a_{i+k-1}$ and $P(a_i) = a_{i+1} a_{i+2} \ldots a_{i+k}$. Since $P(a_{i-1}) > P(a_i)$, this means that $a_i > a_{i+k}$. However, since we set $a_i$ as the minimum value of $a$ this causes a contradiction. Corollary of Main Claim) $a$ is a nondecreasing sequence Explanation: Claim 1 essentially states that for any positive integer $n$, the minimum value of $a_{[n,\infty)}$ is $a_n$. Thus, using induction with $n = 1, 2, \ldots$ shows that $a$ must be nondecreasing. We now split the proof into two cases: $\textbf{Case 1}$) $a$ has a maximum value This means that there exists some positive integer $n$ such that for all $i \geq n$, $a_i = w$ ($w$ is a constant) Thus, $P(w) = w^k$, implying that $P(x) = x^k$. Therefore, $P(a_{n-1}) = (a_{n-1})^k = a_n a_{n+1} \ldots a_{n+k-1} = w^k$, which means that $a_{n-1} = w$. Repeating this logic for $n-2, n-3, \ldots, 1$ shows that $a_i = w$ for all $i$. We have obtained our first solution. $\textbf{Case 2}$) $a$ doesn't have a maximum value This means that sequence $a_i$ increases indefinitely as $i$ increases Claim) $a$ is strongly increasing Assume $a_i = a_{i+1}$ for some $i$. Since $P(a_i) = P(a_{i+1})$, we can see that $a_{i+1} = a_{i+k+1}$. Since $a$ is nondecreasing, this means that all numbers $a_i$ through $a_{i+k+1}$ are equal. Repeating this logic while increasing $i$ shows that $a$ becomes a constant sequence, causing a contradiction. Let $Seq(i) = (a_{i+1}-a_i, a_{i+2} -a_i, \ldots, a_{i+k}-a_i)$. $Seq(i,j)$ denotes the $j$th element in the $k$-element permutation $Seq(i)$ Set $N$ as a very, very large positive integer. Then, we can safely say that all $a_i$ for $i>N$ is close to infinity as $a$ has no upper bound. Claim 2) For all $i>N$ $Seq(i)$ must be a constant pf) Assume $Seq(i) \neq Seq(i+1)$ for some very large $i > N$ Let $P_1(x) = \Pi_{j=1}^k (x + Seq(i)(j))$ and $P_2(x) = \Pi_{j=1}^k (x + Seq(i+1)(j))$. Then, we can see that $P(a_i) = P_1(a_i)$ and $P(a_{i+1}) = P_2(a_{i+1})$. Since $P_1 \neq P_2$, at least one of the functions $P - P_1$ and $P - P_2$ cannot be a zero function with all coefficients equal to $0$. WLOG, assume that $P - P_1$ is nonnegative. Since both $P$ and $P_1$ have nonnegative coefficients, $P - P_1$ cannot have any coefficients that are larger than $max(c_0,c_1,\ldots,c_{k-1})$. However, since we set $a_i$ as a very, very large positive integer it cannot be a solution of $P - P_1$. Thus, there is a contradiction. Thus, $Seq(i)$ eventually becomes constant for $i > N$, which means $a$ must be an arithmetic sequence (this is trivial by induction working backwards from $N$ to $1$). We have obtained our second solution. Note: The explanation for Claim 2 definitely could be improved (it is possible a very large negative coefficient in $P_1$ overrides the large value of $a_i$), but the intuition should be very clear.

Here's my submission at the IMO. I missed the slick finish from the official solution, though I think my approach is much more motivated. The answer is all infinite arithmetic progressions of positive integers. These work because if $a_{n} = \lambda_{1} + (n-1)\lambda_{2}$ for some integers $\lambda_{1} >0$, $\lambda_{2} \geq 0$ we can pick $P(x) = (x+\lambda_{2})(x+2\lambda_{2})\cdots(x+k\lambda_{2})$ and the polynomial identity will be satisfied. We show that no other sequences work. Main claim. The key step is recognizing that the sequence $\{a_{i}\}_{i=1}^{\infty}$ is strictly increasing if it's not constant. Proof: The idea is to show that if $d = \min_{m \in \mathbb{N}} a_{m}$ and there exists some $t > 1$ with $a_{t} = d$, then the sequence is constant. Assume that's not the case. If $a_{t-1} > d$, compare $P(a_{t-1})$ and $P(a_{t})$: \[a_{t+1}a_{t+2}\cdots a_{t+k} = P(a_{t}) < P(a_{t-1}) = a_{t}a_{t+1}\cdots a_{t+k-1} \Longrightarrow a_{t+k} < a_{t} = d = \min_{m\in\mathbb{N}} a_{m}\]with the inequality holding true due to all the $c_{i}$ being nonnegative. The last inequality $a_{t+k-1} < d$ is clearly impossible, so we derive a contradiction in this case. If $a_{t-1} = d$, comparing $P(a_{t-1})$ and $P(a_{t})$ implies that $a_{t+k} = a_{t} = d$ and we just proved that if $a_{i} = d$ for $i>1$, then $a_{i-1} = d$ as well, we get that $a_{t-1} = a_{t} = a_{t+1} = \cdots = a_{t+k} = d$ by backwards induction from $a_{t+k} = d$. Repeating this argument for $a_{t}$ and $a_{t+1}$ we get that $a_{t+k+1} = d$ as well and continuing on forward, the sequence $\{a_{i}\}_{i>t-2}$ is constant. We can also show that the beginning of the sequence attains that same constant value: \[a_{t-1}a_{t-1}\cdots a_{t+k-2} = P(a_{t-2}) \geq P(d) = P(a_{t-1}) = a_{t}a_{t+1}\cdots a_{t+k-1}\]However, the leftmost and rightmost expressions are both equal to $d^{k}$ which is possible only if $a_{t-2} = d$. Inducting downward, we get that $a_{t-3} = d$ and so on as well, so the sequence is indeed constant. Thus we've proven that $a_{1} = d$ and $a_{1} < a_{i}$ for all $i>1$. It remains to be noticed that if $\{a_{i}\}_{i=1}^{\infty}$ satisfies the desired condition, then we can delete the first few terms of the sequence without any problem, so the above argument also shows that $a_{2} < a_{i}$ for all $i>2$ and so on, $a_{1} < a_{2} < a_{3} < \cdots$, hence the sequence is indeed strictly increasing. Structure claim. There exist integers $0 < m_{1} < m_{2} < \dots < m_{k}$ such that $P(x) = (x+m_{1})(x+m_{2})\cdots (x+m_{k})$. Proof: Let $S = \sum\limits_{i=0}^{k-2} c_{i}$. Call a positive integer $n$ big if $n>S$. For all big integers, we have that $P(n) < n^{k} + (c_{k-1}+1)n^{k-1}$ as \[P(n) = n^{k} + c_{k-1}n^{k-1} + \sum\limits_{i=0}^{k-2} c_{i}n^{i} \leq n^{k} + c_{k-1}n^{k-1} + n^{k-2}\sum\limits_{i=0}^{k-2} c_{i} < n^{k} + (c_{k-1}+1)n^{k-1}\]As the sequence is strictly increasing, all but finitely many of the $a_{i}$ are not big. Denote $b_{i,j} = a_{i} - a_{j} > 0$ for $i>j$. For big $a_{i}$, we have that \[a_{i}^{k} + (c_{k-1}+1)a_{i}^{k-1} > P(a_{i}) = \prod\limits_{j=1}^{k} (a_{i}+b_{i+j, i}) > a_{i}^{k} + b_{i+j, i}a_{i}^{k-1}\]For any $1\leq j\leq k$. Thus $b_{i+j, i} \leq c_{k-1}$, so the differences $a_{i+1} - a_{i}$ are bounded by a constant for big $a_{i}$. Therefore the $k$-tuple $(b_{i+1, i}, b_{i+2, i}, \cdots, b_{i+k, i})$ can take on finitely many (at most $c_{k-1}^{k}$) values, so by the PHP there exists a tuple $(e_{1}, e_{2}, \cdots, e_{k})$ such that \[P(a_{i}) = (a_{i} + e_{1})(a_{i} + e_{2}) \cdots (a_{i} + e_{k})\]holds for infinitely many positive integers $i$. This forces the polynomial $P(x) - \prod\limits_{i=1}^{k} (x+e_{i})$ to have infinitely many distinct real roots, hence must be the constant zero and the claim is proved as clearly $e_{1} < e_{2} < \cdots < e_{k}$ because the sequence $\{a_{i}\}$ is strictly increasing. Finish. We first show that $m_{i+1} - m_{i}$ is constant and then that $a_{i+1} - a_{i}$ is constant. Proof: We work with sufficiently large $a_{i}$. Notice that: \[a_{n}^{k-1} < a_{n+2}a_{n+3}\cdots a_{n+k} \leq \gcd(P(a_{n}), P(a_{n+1})) \leq \prod\limits_{i=1}^{k} \gcd(a_{n}+m_{i}, P(a_{n+1}) ) \leq \prod\limits_{i=1}^{k} \prod\limits_{j=1}^{k} \gcd(a_{n}+m_{i}, a_{n+1}+m_{j})\]Consider a $k \times k$ table with entiries $\gcd(a_{n}+m_{i}, a_{n+1}+m_{j})$ in the cell $(i, j)$. For a fixed $i$ consider the quantity $\gcd(a_{n}+m_{i}, a_{n+1}+m_{j})$ ranging over all $j$. Notice that since $n$ is big, we have that: \[a_{n+1}+m_{j}-a_{n}-m_{i} = m_{j} + b_{n+1, n} - m_{i} \leq 2c_{k-1}-1\]hence if $a_{n}+m_{i} \neq a_{n+1}+m_{j}$, their gcd is bounded from above by a constant. This impies that there's at most one entry $a_{n}+m_{i} < 2a_{n}$ (because $n$ is sufficiently large and $b_{n+i, n}$ is bounded) in the $i$-th row and all other entries must be at most some constant $C = 2c_{k-1}-1$. However, notice that for any $j$ we have: \[a_{n}+b_{n+1, n} = a_{n+1} < a_{n+1} + m_{j}\]therefore the product of the entries in the first row is bounded by $C^{k}$. Now, for the remaining $k-1$ rows, if we assume that for some $i$ there doesn't exist a $j$ such that $a_{n}+m_{i} = a_{n+1} + m_{j}$, then the product of all entries is bounded from above by \[C^{2k}\cdot 2^{k-2} \cdot a_{n}^{k-2} < a_{n}^{k-1}\]for sufficiently large $n$ which is a contradiction with the previously established inequality. Hence for every $i>1$ there exists a $j$ such that $a_{n}+m_{i} = a_{n+1}+m_{j}$. Clearly $j = k$ is too big to satisfy such an equality for any $i\leq k$, but also \[m_{2} < m_{3} < \cdots < m_{k}\]\[m_{1} < m_{2} < \cdots < m_{k-1}\]hence we must have $a_{n} + m_{i} = a_{n+1} + m_{i-1}$. This shows that \[0 = (a_{n} + m_{i}) - (a_{n+1} + m_{i-1}) = (a_{n}-a_{n+1}) - (m_{i-1}-m_{i})\]proving that $m_{i} - m_{i-1}$ is constant, say $m_{i} - m_{i-1} = L$ and furthermore, for sufficiently large $n$ we have that $a_{n+1}-a_{n} = L$, hence the sequence is eventually an arithmetic progression. Having that in mind, assume that $\{a_{n}\}_{n\geq N}$ is an arithmetic progression. Then \[P(a_{N-1}) = a_{N}a_{N+1}\cdots a_{N+k} = \prod\limits_{i=1}^{k} (a_{N}+L(i-1)) = P(a_{N}-L)\]which implies that $a_{N-1} = a_{N} -L$ as all the coefficients of $P$ are nonnegative, so if $a<b$, then $P(a) < P(b)$. Inducting downward, in the same manner, shows that every element of the sequence must be part of this increasing arithmetic progression. We showed that these sequences work, so the problem is solved.

ridiculous (shows my alg skill issue, took like >4 hours not including customizing text editor colors so my eyes weren't murdered every time i tried to write this up)

It would be interesting to relax some of the conditions in this problem, but it seems like pretty much all of them are necessary to make the problem tractable. Th3Numb3rThr33 wrote: My solution is the same as everyone else’s. Here is a solution path by observing the strength of the conditions in the problem statement, at least for $k=2$. The sequence $a$, $b$, $c$, $a$, $b$, $c$, $a$, $\ldots$ works if we let $P(x) = x^2 -(a+b+c)x+(ab+bc+ca)$, so we must use the fact that all coefficients of $ P$ are nonnegative. This suggests that $P$ monotonically increasing is important (which we can use to show $a_i$ nondecreasing). The sequence $1$, $2$, $4$, $8$, $\ldots$ works if we let $P(x) = 8x^2$, so we must use the fact that $P$ is monic. This suggests that something like $x^{-k+1}P(x) - x$ is bounded is important (which we can use to show $a_{i+1}-a_i$ bounded). Then the finish is by the same Pigeonhole argument on “constellations” as everyone else. Adding onto the list of pathological examples, even if we only allow $a_i$ to be arbitrary integers rather than nonnegative and keep all other conditions, we suddenly obtain uncountably many solutions for $k=2m$ even: given any positive integers $r_1,\ldots,r_{2m}$, we may arbitrarily concatenate $0,-r_{\pi_1},\ldots,-r_{\pi_{2m}}$ for arbitrary permutations $\pi$ of $1,\ldots,2m$, and this sequence will work for the polynomial $P(x)=(x+r_1)\cdots(x+r_{2m})$. Similarly, for any positive integers $r_1,\ldots,r_{k-1}$, any sequence consisting of elements of $\{0,-r_1,\ldots,-r_{k-1}\}$ with no consecutive block of nonzero integers of length $k$ will work for the polynomial $P(x)=x(x+r_1)\cdots(x+r_{k-1})$.

Solution from Twitch Solves ISL: 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. Claim: Either $a_1 < a_2 < \cdots$ or the sequence is constant. Proof. Note that \begin{align*} P(a_{n-1}) &= a_{n}a_{n+1}\cdots a_{n+k-1} \\ P(a_n) &= a_{n+1}a_{n+2}\cdots 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 ${\mathbb N}$. 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 \cdots$. 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. $\blacksquare$ Claim: There exists a constant $C$ (depending only $P$, $k$) such that We have $a_{n+1} \leq a_n + C$. Proof. Let $C$ be a constant such that $P(x) < x^k + Cx^{k-1}$ for all $x \in {\mathbb N}$ (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. \end{align*}$\blacksquare$ 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) \coloneqq (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 also means that 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.

Answer: Any arithmetic progression satisfies the problem condition. Firstly, let $(a_n)_{n\ge 1}$ be an arithmetic progression with difference $d$. Then taking $P(x) = (x+d)(x+2d)\cdots (x+dk)$ works. Now we'll prove that the sequence $(a_n)_{n\ge 1}$ is an arithmetic progression. Consider the following claim: Claim: $a_n \le a_{n+1}$ for all $n \ge 1$. Proof. Assume the contrary, $a_n > a_{n+1}$ for some $n$. Then note that $P$ increases on $[0, \infty)$, hence $P(a_n) > P(a_{n+1})$, which means $a_{n+1}a_{n+2}\cdots a_{n+k} > a_{n+2}a_{n+3}\cdots a_{n+k+1}$, or equivalently $a_{n+1} > a_{n+k+1}$. Hence there exists $n_1$ such that $a_{n_1} > a_{n_1+1} \le a_{n_1+2} \le \dots \le a_{n+k+1}$. Thus $a_{n_1+1} < a_{n+k+1} < a_{n+1} < a_{n}$, so replacing $n \to n_1$ and repeating the same argument on $n_1$, we get there exists $n_2$ such that $a_{n_2} > a_{n_2+1}$ and $a_{n_2+1} < a_{n_1+1} < a_{n+1}$. Thus repeating same argument over and over, we get there exists an increasing sequence $(n_k)_{k\ge 0}$ such that $a_{n_i+1} > a_{n_{i+1}+1}$ for all $i \ge 0$, so $a_{n_0+1} > a_{n_1+1} > a_{n_2+1} > \dots >$, contradicting the fact that the sequence $(a_n)_{n\ge 1}$ takes positive integer values. $\blacksquare$ Thus by claim, $a_{n+i} - a_n \ge 0$ for all $1 \le i \le k$. Claim: $a_{n+k} - a_n$ is bounded above. Proof. Suppose $a_{n+k} - a_n$ takes arbitrarily large values. Since $\deg(P) = k$, so there exists $c$ such that $P(x) < (x+c)^k$ for all $x > 0$. Let $N$ be a sufficiently large integer. Then there exists $n$ such that $a_{n+k} - a_n \ge N$. So $a_n^k + N \cdot a_n^{k-1} = a_n^{k-1}(a_n+N) \le a_{n+1}a_{n+2}\cdots a_{n+k} = P(a_n) < (a_n+c)^k$, contradicting $N$ is sufficiently large. $\blacksquare$ Let $S_n$ be $k-$tuplet of integers $(a_{n+1} - a_n, a_{n+2} - a_n, \dots, a_{n+k} - a_n)$. We say that tuplets $(a_1, a_2, \dots, a_k)$ and $(b_1, b_2, \dots, b_k)$ are equal if and only if $a_i = b_i$ for $1 \le i \le k$. Then by claim, all integers in any tuplets doesn't exceed a certain integer, so by infinite pigeonhole principle, there exists an increasing sequence $(i_n)_{n\ge 1}$ such that $S_{i_1} = S_{i_2} = \dots$. Let $d_j = a_{i_1 + j} - a_{i_1}$ for $1 \le j \le k$ and let $Q(x) = (x+d_1)(x+d_2)\cdots (x+d_k)$. Then we have $Q(a_{i_n}) = P(a_{i_n})$ for all $n \ge 1$, which means $a_{i_n}$ is root of $P(x) - Q(x)$, which means $P(x) = Q(x)$ or the sequence $(a_n)_{n\ge 1}$ is eventually constant. If the sequence $(a_n)_{n\ge 1}$ is eventually constant, then $P(x) = x^k$ and backward induction shows that $(a_n)_{n\ge 1}$ is constant sequence. Thus we can assume $(a_n)_{n\ge 1}$ is nonconstant sequence, and thus we get $P(x) = Q(x) = (x+d_1)(x+d_2)\cdots (x+d_k)$. If there exists an increasing sequence $(j_n)_{n\ge 1}$ such that $S_{j_1} = S_{j_2} = \dots$ and $S_{j_1} \neq S_{i_1}$, then we get $\prod_{a \in S_{i_1}}(x+a) = P(x) = \prod_{a \in S_{j_1}}(x+a)$, which is an evident contradiction. Hence for sufficiently large integer $n$, we get $S_n = S_{i_1}$. Therefore $a_{n+i} - a_n = d_i$ for all sufficiently large integer $n$, which means $d_i + d_j = d_{i+j}$ for all $1 \le i, j \le k$ satisfying $i + j \le k$, which shows that $d_i = i \cdot d$ for some $d \ge 0$. Thus the sequence $(a_n)_{n\ge 1}$ eventually becomes an arithmetic progression. Now backward induction shows that $(a_n)_{n\ge 1}$ is an arithmetic progression, as required. $\blacksquare$

We will prove that the only sequences that work are arithmetic sequences. Claim: $a_n$ is non-decreasing Let $a_i$ be a minimum of the sequence. If $a_1$ is a unique minimum, then "delete" this term, shift indices down by $1$, and repeat the process. If the process repeats infinitely than obviously $a_n$ is non-decreasing. If not however, then we proceed with the following. We have $$a_iP(a_i) = a_{i+k}P(a_{i-1})$$If $a_{i-1} \neq a_i$ then we simply have $a_i > a_{i+k}$ which is a clear contradiction. Therefore $a_{i-1} = a_i$, and even further all $a_j = a_i$ for $j < i$. Note that $a_i = a_{i+k}$ and we can repeat the process for $a_{i+k}$ as it is a minimum. From this we can "induct" to prove that $a_n$ must be constant which clearly means it is non decreasing. We now let $b_n \coloneq a_{n+1} - a_n$ and prove the following claim. Note that $b_n$ is nonnegative for all $n$. Claim: $b_n$ is bounded above Assume FTSOC that $b_n$ is not bounded and achieves arbitrarily large values. Observe that \begin{align*} P(a_n) = \prod_{i=1}^{k} a_{n+i} \\ = \prod_{i=0}^{k} \left(a_n + \sum_{j=0}^{i} b_{n+j}\right) > (a_n+b_n)^k\end{align*} Now since $b_n$ can achieve arbitrarily large values, we can select the index $n$ where $b_n > \frac{c_i}{{k \choose i}}$ for all $i$ and we have a clear contradiction. Now there are obviously a finite amount of possibilities of $k$-tuples $\left(b_n, b_{n+1}, \dots, b_{n+k-1}\right)$ where $n$ varies, but obviously an infinite amount of tuples that exist, so by PHP there exists a tuple that appears infinitely many times. This implies that $$P(a_n) = \prod_{i=0}^{k} \left(a_n + \sum_{j=0}^{i} b_{n+j}\right)$$for infinitely many $a_n$ so we have $$P(x) = \prod_{i=0}^{k} \left(a_n + \sum_{j=0}^{i} b_{n+j}\right)$$as a polynomial identity. Now, this immediately implies that all other $k$-tuples appear only a finite amount of times, which also implies that eventually this special $k$-tuple should be the only one that appears. This is only possible if $b_n = b_{n+1} = b_{n+2} = \dots = b_{n+k-1}$ We now finish by inducting down. FTSOC assume the index $i$ is the minimum value where $a_i$ "starts" behaving like an arithmetic sequence (Ex. $a_k = a_{k-1} + d$ for all $k \ge i+1$). Now we have $$P(a_{i-1}) = \prod_{j = 1}^{k} \left(a_{i-1} + j \cdot d\right) = \prod_{j = 0}^{k-1} \left(a_{i} + j \cdot d\right)$$which directly implies $a_{i-1} + d = a_i$, so we can just induct all the way down.

We prove that only arithmetic sequences work. Suppose $a_1,a_2,\ldots$ is a sequence that works. Claim 1: $P(x)$ is strictly increasing and injective polynomial for $x>0$. Proof. Take $a,b$ such that $a>b>0$. Since $c_i$ are non-negative numbers, we have $c_ia^i \leq c_ib^i$ for each $1\leq i\leq k$, and the inequality is strict for $i=k$. Adding, we get that $P(a) > P(b)$, as desired. $\blacksquare$ Since the polynomial is strictly increasing, it is naturally injective as well. Claim 2: $a_{n+1}> a_n$ for each $n\in\mathbb{N}$, or $a_n\equiv C'$ for each $n\in\mathbb{N}$. Proof. Suppose $a_{n+1} < a_n$. Then, \[P(a_{n+1}) < P(a_{n})\Longrightarrow \frac{a_{n+k+1}}{a_{n+1}}\cdot P(a_{n}) < P(a_{n})\Longrightarrow a_{n+k+1} < a_{n+1}\]Consider the minimum from $\{a_n,a_{n+1},\ldots,a_{n+k-1}\}$. If $a_{n+t}$ is the minimum with $t\geq 1$, then $a_{n+t+k} < a_{n+t}$, which means minimum of $\{a_{n+k},a_{n+k+1},\ldots,a_{n+2k-1}\}$ is at most $a_{n+t}-1$. Continuing, we get contradiction, unless $a_n=a_{n+1}=\cdots=a_{n+t}$. Shifting $n$ front and back, we get that all terms are equal to some constant, $C'$ (which is the constant A.P.). $\blacksquare$ Claim 3: $a_{n+1}-a_{n}<C$, for some constant $C$. Proof. Take $C$ such that for each $0\leq i < k$, we have that $\binom{k}{i}C^{k-i} > c_i$. Then, $(x+C)^k > P(x)$ for each $x>0$. Finally, note \[(a_n+C)^k=P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}\geq a_{n+1}^k\Longrightarrow a_n+C\geq a_{n+1}\Longrightarrow a_{n+1}-a_n\leq C,\]as claimed. $\blacksquare$ Claim 4: $a_{n+1}-a_{n}$ is constant. Proof. If $a_{n}=a_{n+1}$ for any $n$ then the sequence is constant, from Claim 2. Assume that the sequence is not constant. Then, from Claim 2, it is strictly increasing, which means that it is unbounded above. So, it achieves infinitely many distinct positive integer values. Note that $\{a_{n+1}-a_{n},a_{n+2}-a_{n+1},\ldots,a_{n+k+1}-a_{n+k}\}\subseteq\{1,2,\ldots,C\}$. Since there are only finitely many subsets (at most $2^C-1$) possible, at least one subset appears infinitely many times for sufficiently many $n$. Suppose that ordered tuple is \[(a_{n+1}-a_{n},a_{n+2}-a_{n+1},\ldots,a_{n+k+1}-a_{n+k})=(b_1,b_2,\ldots,b_{k+1}).\]This means \[P(x)=\left(x+b_1\right)\left(x+b_1+b_2\right)\cdots\left(x+\sum_{i=1}^{k}b_i\right)\]for infintely many $x=a_n$. Since $\deg P=k$ is finite, it means that the above equation is an identity. Similarly, \[P(x)=\left(x+b_2\right)\left(x+b_2+b_3\right)\cdots\left(x+\sum_{i=2}^{k+1}b_i\right)\]is an identity. Comparing, we get that $b_1=b_2$ by noticing that $P\left(-b_1\right)=P\left(-b_2\right)=0$. Then, substituting $x+b_2$ as $x$, we obtain $b_1=b_3$ and so on. Eventually, we get $b_1=b_2=\cdots=b_{k+1}$. Hence, $a_{n+1}-a_{n}$ is constant, which means it is an increasing arithmetic sequences. Combining this with the fact that constant sequences work as well, we have that arithmetic sequences. We now provide the construction for arithmetic sequences. Suppose $a_n=a_1+(n-1)d$ for each $n\in\mathbb{N}$. Then, the polynomial \[P(x)=(x+d)(x+2d)\cdots(x+kd)\]works, as $P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$ for each $n\in\mathbb{N}$. The proof is complete. $\blacksquare$

799786 wrote: For each integer $k\geq 2$, determine all infinite sequences of positive integers $a_1$, $a_2$, $\ldots$ 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}\cdots a_{n+k} \]for every integer $n\geq 1$.

The answer is constant and increasing arithmetic sequences only, which work by setting $P(x) = (x+d)(x+2d) \cdots (x+kd)$. Claim. The sequence $\{a_n\}$ is nondecreasing. Proof. Suppose that there is an index $i > N$ with $a_i > a_{i+1}$. Notice that if $a > b > 0$ then $P(a) > P(b)$ as it has nonnegative coefficients. Thus, for any index $j$, with $a_j > a_{j+1}$, we have\[a_{j+1}a_{j+2} \cdots a_{j+k} = P(a_j) > P(a_{j+1}) = a_{j+2}a_{j+3} \cdots a_{j+k+1}\]so in particular $a_j > a_{j+1} > a_{j+k+1}$. Then, for every index $i$, either $a_i \geq a_{i-1}$ or $a_{i-1} < a_i$, implying $a_i > a_{i+k}$ by the previous argument. Thus, there is a subsequence $a_{n_j}$ with $n_{j+1} \in \{n_j + k, n_j - 1\}$ such that $a_{n_{j+1}} \leq a_{n_j}$ for each $j$. Claim. $n_j > i$ for all $j > 1$. Proof. Note that $n_1 = i$ and $n_2 = i+k+1$. Let $n_r$ be the first index less than $i$. Then $n_{r-1} = n_r + 1 = i$, otherwise we contradict minimality. But $a_i = a_{n_{r-1}} \leq a_{n_2} < a_i$, contradiction. $\blacksquare$ In particular, I claim that there are infinitely many indices $j$ with $a_{n_{j+1}} < a_{n_j}$. Suppose that for all $j > M$ equality holds; then we must have $n_{j+1} = n_j - 1$ for all these $j$ by assumption. Then for $A = n_M$, notice that $n_{M+A-i} = A - (A-i) = i$, contradiction. Hence we have constructed an infinite sequence of strictly decreasing positive integers $a_{n_j}$, which is a contradiction. $\blacksquare$ The rest of the proof goes rather quickly. By the previous claim, we will pick $a_n > M$ very large, with $M$ to be determined. Furthermore, let $b_i = a_i - a_{i-1} \geq 0$ for each $i$. Then, the given condition applied on $a_n$ yields that the polynomial \[Q(x) = P(x) - (x+b_{n+1})(x+b_{n+1}+b_{n+2}) \cdots (x+b_{n+1}+b_{n+2} + \cdots + b_{n+k})\]has a root at $a_n > 0$. Claim. $Q \equiv 0$. Proof. Suppose otherwise. Then there is an index $j$ with $c_{k-j} > S_j$, where $S_j$ is the $j$th symmetric sum of $b_{n+1}, b_{n+1}+b_{n+2}, \dots, b_{n+1}+b_{n+2}+\cdots+b_{n+k}$. In particular, as all the $b_i$ are nonnegative integers, there are only finitely many possible values of the $k$-tuple $(b_{n+1}, b_{n+2}, \dots, b_{n+k})$ as $c_{k-j}$ is a constant. Let $i$ be the smallest index for which $c_{k-i} \neq S_i$ (the coefficients are not equal), and let $M_j = \sup |S_j - c_{k-j}|$ across all $k$-tuples $(d_1, d_2, \dots, d_k)$ (note that $M_j$ only depends on the value of $c_{k-j}$) for each $j > i$. It follows that \begin{align*} |Q(a_n) - P(a_n)| &= |c_{k-i}a_n^{k-i} - S_i a_n^{k-i} + c_{k-i-1}a_n^{k-i-1} - S_{i+1} a_n^{k-i-1} + \cdots + c_0 - S_k| \\ &\geq |c_{k-i}-S_i||a_n^{k-i}| - \sum_{j=i+1}^k |a_n^{k-j}| |S_j - c_{k-j}| \\ &\geq a_n^{k-i} - \sum_{j=i+1}^k M_j a_n^{k-j} \\ &\geq a_n^{k-i} - (k-i) \sup_j M_j a_n^{k-i-1}. \end{align*}By taking $a_n > M = (k-i) \sup_j M_j$ (which does not depend on $n$), we have a contradiction, as needed. $\blacksquare$ Hence the roots of $P$ are precisely $-b_{n+1}, -b_{n+1}-b_{n+2}, \cdots$. In particular, repeating the argument for $a_{n+1} > a_n$, we have \[\{b_{n+1}, b_{n+1}+b_{n+2}, \dots, b_{n+1}+\cdots+b_{n+k}\} = \{b_{n+2}, b_{n+2} + b_{n+3}, \dots, b_{n+2} + \cdots + b_{n+k+1}\}\]as all the elements in each set are distinct. But $b_{n+2}$ is less than all of the first element of the first set, so $b_{n+2} = b_{n+1}$. Repeating this argument, we see that $b_n = d$ is constant for all $n > N$. To finish the problem, we just induct down. Given that $b_i = d$ for all $i \geq \ell+2$, we have \[(a_\ell + d)(a_\ell + 2d) \cdots (a_\ell + kd) = P(a_\ell) = (a_\ell + b_{\ell+1})(a_\ell + b_{\ell+1} + d) \cdots (a_\ell + b_{\ell + 1} + (k-1)d).\]Considering this as a polynomial $R$ in $x = b_{\ell + 1} - d$, we have $P(x) = P(0)$ and $P$ is strictly increasing on $(-a_\ell - d, \infty)$, so $x = 0$ and $b_{\ell + 1} = d$, as needed. This completes the induction and shows that $\{a_n\}$ is an arithmetic sequence, as needed.

The answer is all arithmetic sequences with common difference $d \geq 0$. The corresponding polynomial is $P(x)=(x+d)(x+2d) \dots (x+kd)$. Claim 1. $a_n \geq a_{n-1}$ for all $n$. Proof. Suppose FTSOC that $a_n < a_{n-1}$ for some $n$. Then $a_{n+1}a_{n+2} \dots a_{n+k} = P(a_n) < P(a_{n-1}) = a_na_{n+1} \dots a_{n+k-1}$ implies $a_{n+k} < a_n$, so consider the smallest index $n' \in [n+1, n+k]$ satisfying $a_{n'} < a_n$. Then $a_{n'} < a_{n'-1}$ and we can repeat this process to generate a decreasing subsequence of positive integers, contradiction. $\square$ Claim 2. $(a_n)$ is either constant or strictly increasing. Proof. Suppose $a_n = a_{n-1}$. Then $a_{n+1}a_{n+2} \dots a_{n+k} = P(a_n) = P(a_{n-1}) = a_na_{n+1} \dots a_{n+k-1}$ implies $a_{n+k} = a_n$, so by Claim 1 we have $a_n = a_{n+1} = \dots = a_{n+k}$. The given condition implies $P(a_n) \geq a_n^k$, and here equality holds which forces $P(x) = x^k$. We can work backwards to obtain that $(a_n)$ is constant. $\square$ Henceforth suppose $(a_n)$ is strictly increasing. Claim 3. $d_n = a_{n+1} - a_n$ is bounded. Proof. Suppose not. Then consider \[ a_n^k+c_{k-1}a_n^{k-1}+\dots + c_1a_n+c_0 = P(a_n) = a_{n+1}a_{n+2}\cdots a_{n+k} > a_{n+1}^k = (a_n + d_n)^k . \]However, for $d_n$ sufficiently large, each term in the expansion of the RHS will be larger than the corresponding term in the LHS, contradiction. $\square$ Let $S_n = (a_{n+1}-a_n, a_{n+2}-a_n, \dots, a_{n+k}-a_n)$. As each element is bounded by applying Claim 3, there are only finitely possible values for $S_n$. Hence by infinite Pigeonhole there exists $S = (z_1, z_2, \dots, z_k)$ such that $S_n = S$ infinitely often. Claim 4. $P(x) = (x+z_1)(x+z_2) \dots (x+z_k)$. Proof. As $P(x)-(x+z_1)(x+z_2) \dots (x+z_k)$ is a polynomial and equals zero infinitely often, it must be identically zero. $\square$ Claim 5. $S_n = S$ for all sufficiently large $n$. Proof. Let $S_n = (w_1, w_2, \dots, w_k)$. Then \[ (a_n + z_1)(a_n + z_2) \dots (a_n + z_k) = P(a_n) = a_{n+1}a_{n+2}\cdots a_{n+k} = (a_n + w_1)(a_n + w_2) \dots (a_n + w_k) \]and as the $w_i$'s are bounded, we can take $a_n > \max \{ w_1, \dots, w_k, z_1, \dots, z_k \}$. Then if one expands each side, they are valid representations of the same number in base $a_n$, so each corresponding term must be equal which implies $(x + z_1)(x + z_2) \dots (x + z_k) \equiv (x + w_1)(x + w_2) \dots (x + w_k)$. As $w_1 < \dots < w_k$ and $z_1 < \dots < z_k$, we conclude that $S_n = S$ as desired. $\square$ In particular, for sufficiently large $n$ we have $S_{n+1} = S_n$, so $d_{n+1} = d_n$, so $d_n$ eventually equals some constant $d$. By Claim 4 we have $P(x)=(x+d)(x+2d) \dots (x+kd)$ and may work backwards to conclude that $d_n = d$ for all $n$, as desired.

Suppose the minimum of the sequence $a_n$ has the property $a_{n-1}>a_n$ for $n\neq 1$, we get that $a_{n+k}P(a_{n-1})=a_nP(a_n)<a_nP(a_{n-1})$ which is a contradicition as we know a minimum must exist. Thus $a_n$ is non strictly increasing. Note that there exists a value $y$ such that $(x+y)^k\geq P(x)$ for all $x$. Thus we get that $a_{n}+y\geq a_{n+1}$ from the non decreasing. This suffices to prove that it is bounded, from pigeon hole plus FTOA we get that is must be an arithmetic progression.

Please contact westskigamer@gmail.com if there is an error with any of my solution for cash bounties by 3/18/2025. Note on above: The beef is this solution is the same as Evan's so idt it's likely there'll be an error here