Problem 3: For each integer \(k \geqslant 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}+\cdots+c_1 x+c_0\), where \(c_0, c_1, \ldots, c_{k-1}\) are non-negative integers, such that
\[P\left(a_n\right)=a_{n+1} a_{n+2} \cdots a_{n+k}\]for every integer \(n \geqslant 1\).
Solution 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\)
Solution 2. 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.
Solution 3. The answer is nondecreasing arithmetic sequences only. These work, since if the common difference is \(d\), we can write the polynomial \((x+d)\ldots(x+kd)\). We now prove that they are the only ones.
First, if all the \(c_i\) are zeroes, we may pick some prime \(p \mid a_1\) and examine the \(p\)-adic valuation of the sequence, which satisfies \(k\nu_p(a_n)=\nu_p(a_{n+1})+\cdots+\nu_p(a_{n+k})\). Since these should all be nonnegative integers, pick \(n\) with \(\nu_p(a_n)\) minimal; then \(\nu_p(a_{n+1}),\ldots\) are all minimal by induction, so working backwards we find that \(\nu_p(a_{n-1}),\nu_p(a_{n-2}),\ldots\) are all minimal by induction as well, i.e. the sequence is constant. Thus suppose at least one of the \(c_i\) is positive.
Claim 1: There does not exist a constant \(C\) such that we can find arbitrarily large \(n\) with
\[a_{n+1},\ldots,a_{n+k} \leq C.\]Proof: For every \(n\) there exists some \(1 \leq i \leq k\) such that \(a_{n+i}>a_n\), else \(P(a_n)\leq a_n^k\). Then, we can essentially repeat this to find some \(a_m>C\), and then repeat it more to get some sequence of terms separated by distance at most \(k\), all exceeding \(C\). \(\blacksquare\)
Claim 2: There does not exist a constant \(C\) such that we can find arbitrarily large \(n\) with \(a_n \leq C\), i.e. every term in the sequence occurs finitely many times. Proof: If such a \(C\) exists, pick \(n\) large with \(a_n \leq C\). By claim \(1\), we can find some \(1 \leq i \leq k\) such that \(a_{n+i}\) is massive, which is a contradiction by taking \(a_{n+i}>P(C)\). \(\blacksquare\)
The second claim allows us to find infinitely many \(n\) such that \(a_n<a_{n+1},a_{n+2},\ldots\); call such \(n\) endangered. Clearly, \(a_n\) across \(n\) endangered can grow arbitrarily large.
For every endangered \(n\), consider the differences \(a_{n+1}-a_n,\ldots,a_{n+k}-a_n\), which must be at least one. On the other hand, if \(a_n\) is sufficiently large, they must be at most \(100c_{k-1}+100\), so they are all bounded in some interval. Therefore, by Pigeonhole, some multiset of differences \(\{d_1,\ldots,d_k\}:=S\) with \(0<d_1\leq \cdots \leq d_k\) must occur infinitely many times. Writing the RHS as a polynomial in \(a_n\), we get that
\[P(a_n)=(a_n+d_1)\ldots(a_n+d_k)\]for infinitely many choices of \(a_n\), hence this equality must hold in the polynomial sense.
Now we consider \(a_{n+1}\), where \(n\) is endangered and \(\{a_{n+1}-a_n,\ldots,a_{n+k}-a_n\}=S\). Let \(\{a_{n+2}-a_{n+1},\ldots,a_{n+k}-a_{n+1},a_{n+k+1}-a_{n+1}\}=S'\) (both sides are multisets), where \(d_1' \leq \cdots \leq d_k'\). The elements \(a_{n+2}-a_{n+1},\ldots,a_{n+k}-a_{n+1}\) are bounded (in both directions), since they are in \(S-S\), hence for \(a_{n+1}\) sufficiently large, \(a_{n+k+1}-a_{n+1}\) must be bounded in both directions as well, otherwise we get a size contradiction. Therefore by Pigeonhole some choice of differences \(\{d_1',\ldots,d_k'\}:=S'\) appears infinitely many times, for infinitely many \(a_{n+1}\) (since \(a_{n+1}>a_n\) grows arbitrarily large), so we get that \(P(a_{n+1})=(a_{n+1}+d_1')\ldots(a_{n+1}+d_k')\) holds infinitely many times, hence it must be a polynomial equality. But since polynomials have unique factorizations, it follows that \(S=S'\). It is then clear that \(a_{n+1}-a_n=d_1\), since otherwise \(S' \ni d_1-(a_{n+1}-a_n)\leq 0\), but \(S\) contains only positive integers. From here, we find that \(d_2-d_1=d_1'\), since if it is less then it can’t be in \(S'\) and if it is more then there is no way we can find \(d_1'\) in \(S-d_1\), and by induction we have \(d_3-d_1=d_2'\) and so on, until \(d_k-d_1=d_{k-1}'\), implying that \(a_{n+k+1}-a_{n+1}=d_k'\). This actually implies that \(d_i=id_1\) for all \(1 \leq i \leq k\).
Let \(d=d_1\) for convenience. We will perform a “parallel” induction on the two conditions:
\[\{a_{m+1},\ldots,a_{m+k}\}=\{a_m+d,\ldots,a_m+kd\}\] \[a_{m+1}=a_m+d\]For \(m=n\), where \(n\) is endangered, we just proved that these two conditions are true. Pick \(n\) to be large enough as a base case. Now, if the two conditions are true for \(m\), since \(a_{m+1}=a_m+d\) by hypothesis, we have \(\{a_{m+2},\ldots,a_{m+k}\}=\{a_m+2d,\ldots,a_m+kd\}=\{a_{m+1}+d,\ldots,a_{m+1}+(k-1)d\}.\)By dividing out both sides of the given equation by \(a_{m+2}\ldots a_{m+k}\), it follows that \(a_{m+k+1}=a_{m+1}+kd,\) so the first condition is true for \(m+1\). Let \(a_{m+2}=a_{m+1}+id\), so then
\[\{a_{m+3},\ldots,a_{m+k+1}\}=\{a_{m+1}+(1-i)d,\ldots,a_{m+1}+(-1)d,a_{m+1}+d,\ldots,a_{m+1}+(k-i)d\}.\]If \(i \geq 2\), then \(a_{m+1}-d\) is actually in the above set. But by the Euclidean algorithm, since \(d\) is not a root of \(P\), we can write \(P(x)=(x-d)Q(x)+R(x)\) where \(R\) is a nonzero constant polynomial (not dependent on \(n,m\)), so then for \(a_{m+1}\) large, \(\tfrac{P(a_{m+1})}{a_{m+1}-d}\) cannot be an integer, but the product of all the other elements in the above set is clearly integral: contradiction. Hence \(i=1\), so \(a_{m+2}=a_{m+1}+d\), completing the induction.
It now follows that the sequence \(a_1,a_2,\ldots\) is eventually arithmetic (with common difference \(d\)). On the other hand, since the coefficients of \(P\) are all nonnegative, and at least one is positive, it is strictly increasing in \(\mathbb{R}^+\). Therefore, given \(a_{n+1},\ldots,a_{n+k}\), there is exactly one possible choice for \(a_n\) (which is not necessarily an integer). On the other hand, if \((a_{n+1},\ldots,a_{n+k})=(a+d,\ldots,a+kd)\), then it is clear that setting \(a_n=a\) will work, so we must have \(a_n=a\). Therefore, by inducting “downwards”, with base case \(m=n\) and inductive step \(m \to m-1\), it follows that the entire sequence is an arithmetic progression with common difference \(d\), finishing the problem. \(\blacksquare\)