IMO 2023 · 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_1x+c_0\), where \(c_0,c_1,\ldots,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\).

Official text of the problem. Official problem paper (PDF)

Answer

For every \(k\geqslant2\), the sequences are exactly \[ \boxed{a_n=A+(n-1)d\qquad(n\geqslant1),} \] where \(A\) is a positive integer and \(d\) is a non-negative integer. The corresponding polynomial is \[ P(x)=\prod_{i=1}^{k}(x+id). \]

Solution

Suppose that a sequence and polynomial satisfy the given conditions. The polynomial \(P\) is positive and strictly increasing on the positive real numbers. Dividing the equations for consecutive indices gives \[ a_{n+k+1} =a_{n+1}\frac{P(a_{n+1})}{P(a_n)} \qquad(n\geqslant1). \tag{1} \]

We first prove that the sequence is nondecreasing. Fix \(r\geqslant1\), and let \(a_j\) be the first occurrence of the minimum of \[ a_r,a_{r+1},a_{r+2},\ldots. \] This minimum exists because the terms are positive integers. If \(j>r\), then \(a_{j-1}>a_j\), so (1) yields \[ a_{j+k} =a_j\frac{P(a_j)}{P(a_{j-1})} <a_j, \] contradicting the choice of the minimum. Thus \(j=r\). In particular, \(a_r\leqslant a_{r+1}\), proving the assertion.

If the sequence is bounded, it is eventually constant, say equal to \(A\). Then \(P(A)=A^k\), so nonnegativity of the coefficients implies that all \(c_i\) vanish. Consequently, for every \(n\), \[ a_n^k=P(a_n)=\prod_{i=1}^{k}a_{n+i} \geqslant a_{n+1}^k \geqslant a_n^k. \] Hence \(a_{n+1}=a_n\) for every \(n\), giving the required solution with \(d=0\).

We may therefore assume that the sequence is unbounded. Its monotonicity then gives \(a_n\to\infty\).

Set \[ C=\sum_{j=0}^{k-1}c_j, \qquad d_n=a_{n+1}-a_n\geqslant0. \] For \(x\geqslant1\), we have \(P(x)\leqslant x^k+Cx^{k-1}\). Using monotonicity and the binomial theorem, we obtain \[ a_n^k+kd_na_n^{k-1} \leqslant(a_n+d_n)^k =a_{n+1}^k \leqslant P(a_n) \leqslant a_n^k+Ca_n^{k-1}. \] Thus \[ 0\leqslant d_n\leqslant \frac Ck \qquad\text{for every }n. \tag{2} \]

For \(1\leqslant i\leqslant k\), define \[ b_{n,i}=a_{n+i}-a_n, \qquad Q_n(x)=\prod_{i=1}^{k}(x+b_{n,i}). \] By (2), \[ 0\leqslant b_{n,i} =\sum_{j=0}^{i-1}d_{n+j} \leqslant\frac{iC}{k} \leqslant C. \] All these offsets are integers, so there are only finitely many possible polynomials \(Q_n\). Moreover, the original equation says \[ P(a_n)=Q_n(a_n). \tag{3} \]

Each possible polynomial \(Q\neq P\) can satisfy \(P(x)=Q(x)\) at only finitely many real numbers. Since there are finitely many such \(Q\), and \(a_n\to\infty\), equation (3) implies that there is an index \(N\) such that \[ Q_n=P\qquad\text{for every }n\geqslant N. \tag{4} \]

Now \[ b_{n,1}\leqslant b_{n,2}\leqslant\cdots\leqslant b_{n,k}, \] so the largest real root of \(Q_n\) is \(-b_{n,1}=-d_n\). By (4), this root is independent of \(n\geqslant N\). Therefore \[ d_n=d\qquad(n\geqslant N) \] for some integer \(d\geqslant0\). Unboundedness excludes \(d=0\). The sequence is thus an arithmetic progression from index \(N\) onward, and (4) gives \[ P(x)=\prod_{i=1}^{k}(x+id). \tag{5} \]

It remains to extend this progression backward. Suppose that the terms from index \(m>1\) onward form an arithmetic progression with difference \(d\). By (5) and the equation at index \(m-1\), \[ \prod_{i=1}^{k}(a_{m-1}+id) = \prod_{j=0}^{k-1}(a_m+jd). \] The function \[ H(t)=\prod_{j=0}^{k-1}(t+jd) \] is strictly increasing for \(t>0\), since all its factors are positive and strictly increasing there. The preceding equality is \[ H(a_{m-1}+d)=H(a_m), \] so \(a_m=a_{m-1}+d\). Repeating this argument backward proves \[ a_n=a_1+(n-1)d \qquad\text{for every }n\geqslant1. \]

Conversely, let \(a_n=A+(n-1)d\), where \(A\geqslant1\) and \(d\geqslant0\) are integers. The polynomial \[ P(x)=\prod_{i=1}^{k}(x+id) \] is monic of degree \(k\) and has non-negative integer coefficients. It satisfies \[ P(a_n)=\prod_{i=1}^{k}(a_n+id) =\prod_{i=1}^{k}a_{n+i}, \] as required.

The solution was checked against the official IMO shortlist solutions.