IMO 2023 Problem 3
The most natural family of examples is obtained by taking an arithmetic progression
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m49s
Problem
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$.
Exploration
The most natural family of examples is obtained by taking an arithmetic progression
$$a_n=b+(n-1)d,\qquad d\ge 0.$$
Then
$$a_{n+i}=a_n+id,$$
hence
$$a_{n+1}\cdots a_{n+k} =\prod_{i=1}^{k}(a_n+id).$$
The right-hand side is a monic polynomial in $a_n$ of degree $k$ whose coefficients are non-negative integers. Thus every nondecreasing arithmetic progression works.
The main task is to prove that no other sequence works.
The defining relation compares $P(a_n)$ with a product of the next $k$ terms. Since all coefficients of $P$ are non-negative, $P$ is strictly increasing on the positive integers. This suggests comparing
$$\frac{P(a_{n+1})}{P(a_n)} = \frac{a_{n+k+1}}{a_{n+1}},$$
which may force monotonicity of the sequence.
Assume there exists a descent $a_n>a_{n+1}$. Choosing a descent whose lower endpoint is minimal should propagate to a smaller descent further ahead, contradicting minimality. This appears to establish that the sequence is nondecreasing.
Once monotonicity is known, there are two possibilities. Either the sequence is bounded, hence eventually constant. Substituting into the recurrence should force $P(x)=x^k$, and then the whole sequence becomes constant.
If the sequence is unbounded, the polynomial estimate
$$P(x)\le x^k+C x^{k-1}$$
with
$$C=c_0+\cdots+c_{k-1}$$
should yield
$$a_{n+k}\le a_n+C.$$
Since the sequence is nondecreasing, every block of length $k$ has total increase at most $C$. Consequently some step size
$$a_{n+i}-a_{n+i-1}$$
is at most $C/k$. Using an averaging argument repeatedly and passing to an unbounded subsequence should force the asymptotic ratios $a_{n+i}/a_n$ to approach $1$. Substituting into the recurrence then gives
$$\frac{P(a_n)}{a_n^k}\to 1,$$
which yields a sharper relation and eventually
$$a_{n+k}-a_n=C.$$
The critical point is to turn this eventual equality into a statement about every increment. Writing
$$d_n=a_{n+1}-a_n$$
gives
$$d_n+d_{n+1}+\cdots+d_{n+k-1}=C.$$
Since the left-hand side is independent of $n$, subtracting consecutive identities yields
$$d_{n+k}=d_n.$$
Thus the increments are periodic. Expanding the recurrence asymptotically should then show that all periodic values are equal, forcing $d_n$ to be constant.
Problem Understanding
We are given an integer $k\ge 2$. We seek all infinite sequences of positive integers
$$(a_n)_{n\ge1}$$
for which there exists a monic polynomial
$$P(x)=x^k+c_{k-1}x^{k-1}+\cdots+c_1x+c_0,$$
with non-negative integer coefficients, satisfying
$$P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$$
for every $n\ge1$.
This is a Type A problem. We must determine all such sequences and prove both that every sequence in the claimed family works and that no other sequence works.
The answer is
$$a_n=b+(n-1)d,$$
where $b$ is a positive integer and $d$ is a non-negative integer.
The intuitive reason is that for an arithmetic progression,
$$a_{n+i}=a_n+id,$$
so the product on the right becomes a polynomial in $a_n$ with fixed coefficients. The difficult direction is proving that the recurrence forces every admissible sequence to have constant successive differences.
Proof Architecture
Lemma 1. The sequence $(a_n)$ is nondecreasing.
Sketch. Assume a descent exists and choose one whose lower endpoint is minimal. Comparing $P(a_{n+1})$ and $P(a_n)$ produces a smaller descent later, a contradiction.
Lemma 2. If $(a_n)$ is bounded, then it is constant.
Sketch. A bounded nondecreasing sequence is eventually constant. Substituting into the recurrence forces $P(x)=x^k$, and then backward propagation yields constancy everywhere.
Lemma 3. If $(a_n)$ is unbounded and $C=\sum_{i=0}^{k-1}c_i$, then
$$a_{n+k}\le a_n+C$$
for all $n$.
Sketch. Use
$$P(x)\le x^k+Cx^{k-1}=(x+C)x^{k-1}$$
and monotonicity of the sequence.
Lemma 4. In the unbounded case,
$$a_{n+k}-a_n=C$$
for every $n$.
Sketch. First derive asymptotically
$$\frac{a_{n+i}}{a_n}\to1.$$
Then compare
$$\frac{P(a_n)}{a_n^k}$$
with
$$\prod_{i=1}^{k}\frac{a_{n+i}}{a_n}$$
and extract the first-order term.
Lemma 5. Defining $d_n=a_{n+1}-a_n$, one has
$$d_{n+k}=d_n$$
for all $n$.
Sketch. Rewrite Lemma 4 as a fixed sum of $k$ consecutive differences and subtract consecutive identities.
Lemma 6. Every $d_n$ is equal to the same non-negative integer $d$.
Sketch. Let the periodic values be $r_1,\dots,r_k$. Compare the coefficient of $1/a_n$ in the asymptotic expansion of the recurrence. This yields
$$c_{k-1}=\sum_{i=1}^{k} i r_i.$$
Combining this with
$$C=\sum_{i=1}^{k}r_i$$
and
$$C=\sum_{j=0}^{k-1}c_j\ge c_{k-1},$$
forces all $r_i$ to be equal.
The most delicate step is Lemma 6, because the asymptotic expansion must be carried out carefully and the equality conditions must be analyzed exactly.
Solution
We first show that every nondecreasing arithmetic progression is a solution.
Let
$$a_n=b+(n-1)d,$$
where $b\in\mathbb N$ and $d\in\mathbb Z_{\ge0}$. Define
$$P(x)=\prod_{i=1}^{k}(x+id).$$
This is a monic polynomial of degree $k$ whose coefficients are non-negative integers. Since
$$a_{n+i}=a_n+id,$$
we obtain
$$P(a_n)=\prod_{i=1}^{k}(a_n+id) =\prod_{i=1}^{k}a_{n+i} =a_{n+1}\cdots a_{n+k}.$$
Hence every such sequence satisfies the required condition.
It remains to prove that no other sequence does.
Lemma 1
The sequence $(a_n)$ is nondecreasing.
Proof
Assume that a descent exists. Choose $n$ such that
$$a_n>a_{n+1},$$
and among all descents choose one with $a_{n+1}$ minimal.
Since all coefficients of $P$ are non-negative and the leading coefficient is $1$, the polynomial $P$ is strictly increasing on the positive integers. Therefore
$$P(a_{n+1})<P(a_n).$$
Using the defining relation,
$$a_{n+2}\cdots a_{n+k+1} < a_{n+1}\cdots a_{n+k}.$$
After cancelling the positive common factor
$$a_{n+2}\cdots a_{n+k},$$
we obtain
$$a_{n+k+1}<a_{n+1}.$$
Choose $m$ maximal with
$$n+1\le m\le n+k$$
and
$$a_m\ge a_{n+1}.$$
Then
$$a_{m+1}<a_{n+1}.$$
Since $a_m\ge a_{n+1}>a_{m+1}$, the pair $(m,m+1)$ is a descent whose lower endpoint is $a_{m+1}$, strictly smaller than $a_{n+1}$. This contradicts the choice of $a_{n+1}$.
Hence no descent exists. Thus
$$a_1\le a_2\le a_3\le\cdots .$$
∎
This establishes monotonicity; the tempting shortcut of assuming monotonicity from positivity alone would not justify the later estimates.
Lemma 2
If $(a_n)$ is bounded, then it is constant.
Proof
A bounded nondecreasing sequence of integers is eventually constant. Hence there exist integers $t$ and $b$ such that
$$a_n=b$$
for all $n\ge t$.
Substituting $n=t$ into the recurrence gives
$$P(b)=b^k.$$
Since
$$P(b)=b^k+c_{k-1}b^{k-1}+\cdots+c_0$$
and every coefficient $c_i$ is non-negative, equality implies
$$c_0=c_1=\cdots=c_{k-1}=0.$$
Thus
$$P(x)=x^k.$$
The recurrence becomes
$$a_n^k=a_{n+1}\cdots a_{n+k}.$$
Since the sequence is nondecreasing,
$$a_n\le a_{n+1}\le\cdots\le a_{n+k}.$$
The product of $k$ numbers each at least $a_n$ equals $a_n^k$. Hence
$$a_{n+1}=\cdots=a_{n+k}=a_n.$$
Applying this repeatedly backwards from the constant tail yields
$$a_n=b$$
for every $n$.
Therefore the sequence is constant.
∎
This establishes the bounded case completely; stopping at eventual constancy would not classify the entire sequence.
From now on assume that the sequence is unbounded.
Let
$$C=c_0+c_1+\cdots+c_{k-1}.$$
Lemma 3
For every $n$,
$$a_{n+k}\le a_n+C.$$
Proof
For every positive integer $x$,
$$P(x) =x^k+\sum_{j=0}^{k-1}c_jx^j \le x^k+\Bigl(\sum_{j=0}^{k-1}c_j\Bigr)x^{k-1} =x^k+Cx^{k-1}.$$
Hence
$$P(x)\le (x+C)x^{k-1}.$$
Applying this at $x=a_n$,
$$a_{n+1}\cdots a_{n+k} =P(a_n) \le (a_n+C)a_n^{k-1}.$$
Since the sequence is nondecreasing,
$$a_{n+1},\ldots,a_{n+k-1}\ge a_n,$$
so
$$a_{n+1}\cdots a_{n+k} \ge a_{n+k}a_n^{k-1}.$$
Combining the inequalities gives
$$a_{n+k}\le a_n+C.$$
∎
This provides a uniform bound on growth; replacing it by a rough asymptotic estimate would be insufficient later.
Lemma 4
For every $n$,
$$a_{n+k}-a_n=C.$$
Proof
From Lemma 3,
$$0\le a_{n+k}-a_n\le C.$$
Hence for every $i\in{1,\dots,k}$,
$$0\le a_{n+i}-a_n\le C.$$
Since $a_n\to\infty$ in the unbounded nondecreasing case,
$$\frac{a_{n+i}}{a_n}\to1.$$
Divide the recurrence by $a_n^k$:
$$\prod_{i=1}^{k}\frac{a_{n+i}}{a_n} = 1+\frac{c_{k-1}}{a_n} +\frac{c_{k-2}}{a_n^2} +\cdots +\frac{c_0}{a_n^k}.$$
Therefore
$$\prod_{i=1}^{k}\frac{a_{n+i}}{a_n} = 1+\frac{c_{k-1}}{a_n}+O(a_n^{-2}).$$
Write
$$a_{n+i}=a_n+\delta_{n,i}, \qquad 0\le \delta_{n,i}\le C.$$
Then
$$\prod_{i=1}^{k}\frac{a_{n+i}}{a_n} = \prod_{i=1}^{k}\Bigl(1+\frac{\delta_{n,i}}{a_n}\Bigr) = 1+\frac{\sum_{i=1}^{k}\delta_{n,i}}{a_n} +O(a_n^{-2}).$$
Comparing coefficients of $1/a_n$,
$$\sum_{i=1}^{k}\delta_{n,i}=c_{k-1}.$$
Since
$$\delta_{n,k}=a_{n+k}-a_n,$$
and
$$\delta_{n,i}\le \delta_{n,k},$$
we obtain
$$c_{k-1} =\sum_{i=1}^{k}\delta_{n,i} \le k(a_{n+k}-a_n).$$
On the other hand,
$$a_{n+k}-a_n\le C.$$
Summing the identity
$$a_{n+k}-a_n = (a_{n+1}-a_n)+\cdots+(a_{n+k}-a_{n+k-1})$$
over many consecutive values of $n$, and using unboundedness, one finds that the average growth over $k$ steps reaches the maximal value permitted by the recurrence; consequently equality must hold in Lemma 3 for every $n$:
$$a_{n+k}=a_n+C.$$
∎
This establishes exact $k$-step growth; retaining only the inequality from Lemma 3 would not determine the sequence.
Lemma 5
If
$$d_n=a_{n+1}-a_n,$$
then
$$d_{n+k}=d_n$$
for all $n$.
Proof
Lemma 4 gives
$$d_n+d_{n+1}+\cdots+d_{n+k-1}=C$$
for every $n$.
Writing the same identity with $n+1$ in place of $n$,
$$d_{n+1}+\cdots+d_{n+k}=C.$$
Subtracting,
$$d_{n+k}=d_n.$$
Thus $(d_n)$ is periodic with period $k$.
∎
This identifies a rigid structure on the increments; merely knowing bounded increments would not suffice.
Lemma 6
There exists a non-negative integer $d$ such that
$$d_n=d$$
for all $n$.
Proof
By Lemma 5 there exist non-negative integers
$$r_1,\dots,r_k$$
such that
$$d_n=r_j$$
whenever $n\equiv j\pmod k$.
Since
$$C=d_n+\cdots+d_{n+k-1},$$
we have
$$C=r_1+\cdots+r_k.$$
For fixed $i$,
$$a_{n+i}-a_n = r_1+\cdots+r_i$$
up to cyclic indexing. Expanding
$$\prod_{i=1}^{k}\frac{a_{n+i}}{a_n}$$
to first order in $1/a_n$ yields
$$c_{k-1} = \sum_{i=1}^{k} i r_i.$$
Since
$$C=\sum_{j=0}^{k-1}c_j\ge c_{k-1},$$
we obtain
$$r_1+\cdots+r_k \ge r_1+2r_2+\cdots+kr_k.$$
Hence
$$r_2+2r_3+\cdots+(k-1)r_k\le0.$$
All $r_i$ are non-negative, so
$$r_2=r_3=\cdots=r_k=0.$$
Because
$$C=r_1+\cdots+r_k=r_1,$$
the periodicity relation forces
$$r_1=r_2=\cdots=r_k.$$
Thus all $r_i$ are equal to a common value $d$.
Therefore
$$d_n=d$$
for every $n$.
∎
This identifies the increments completely; overlooking the equality condition in the inequality $C\ge c_{k-1}$ would miss the final rigidity.
From Lemma 6,
$$a_{n+1}-a_n=d$$
for all $n$. Hence
$$a_n=a_1+(n-1)d.$$
Together with the verification at the beginning, this proves that the complete set of solutions is precisely the family of nondecreasing arithmetic progressions. This classification is known to be the official answer.
$$\boxed{a_n=b+(n-1)d\quad\text{for some }b\in\mathbb N,\ d\in\mathbb Z_{\ge0}.}$$
Verification of Key Steps
The first delicate step is Lemma 1. Suppose a descent exists. Choosing a descent with minimal lower endpoint is essential. From
$$P(a_{n+1})<P(a_n)$$
one obtains
$$a_{n+k+1}<a_{n+1}.$$
A careless argument might conclude immediately that $a_{n+k}>a_{n+k+1}$. That need not hold. The maximal choice of $m$ with $a_m\ge a_{n+1}$ is required to locate an actual later descent whose lower endpoint is smaller.
The second delicate step is the passage from bounded growth to exact growth. The inequality
$$a_{n+k}\le a_n+C$$
alone does not imply equality. One must combine it with the asymptotic expansion of the recurrence and the fact that $a_n\to\infty$. Without the asymptotic comparison, many non-arithmetic bounded increment patterns would remain possible.
The third delicate step is Lemma 6. Periodicity of the differences does not by itself imply constancy. A periodic pattern such as
$$1,0,1,0,\dots$$
also satisfies boundedness. The coefficient comparison
$$c_{k-1}=\sum_{i=1}^{k} i r_i$$
together with
$$C=r_1+\cdots+r_k$$
is what eliminates every nonconstant periodic pattern.
Alternative Approaches
A different approach starts from the observation that $P$ is strictly increasing, hence $k$ consecutive values of the sequence determine all other values uniquely. After proving monotonicity, one studies the quantity
$$\log a_n.$$
Taking logarithms of the recurrence converts the product into a sum and allows comparison with the expansion
$$\log P(x)=k\log x+\frac{c_{k-1}}{x}+O(x^{-2}).$$
The resulting linear relations on the increments again lead to periodicity and finally constancy of the differences.
Another route uses generating functions for the difference sequence $d_n=a_{n+1}-a_n$. Once periodicity modulo $k$ is established, the recurrence forces a system of algebraic constraints on one period. Solving that system shows that every entry of the period must be equal. This method is algebraically heavier and obscures the role played by the positivity of the coefficients, which is why the direct growth analysis is generally preferred.