Problem 3

For each integer

k\ge2

, 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\ge1

Step 5 of 6: Pigeonhole on the pattern of increments

Previous step Next step

In plain words

Since increments are bounded, the k-tuple of consecutive gaps after any index only has finitely many possible values, so some tuple must repeat infinitely often, and a polynomial identity that holds infinitely often must hold identically.

(d_1,\ldots,d_k)\ \text{recurs}\implies P(X)=\prod_{j=1}^k(X+d_1+\cdots+d_j)

Detailed analysis

For each $n$ let $\delta(n)=(a_{n+1}-a_n,\ldots,a_{n+k}-a_{n+k-1})$ . Step 4 puts every entry in $\{1,2,\ldots,C-1\}$ in the non-constant case, so only finitely many tuples can occur. Choose $(d_1,\ldots,d_k)$ occurring for infinitely many indices $N$ . For every such $N$ , writing $s_j=d_1+\cdots+d_j$ gives $P(a_N)=\prod_{j=1}^k(a_N+s_j)$ . The values $a_N$ are infinitely many distinct integers because the sequence is strictly increasing; therefore the nonzero polynomial $P(X)-\prod_{j=1}^k(X+s_j)$ cannot vanish at all of them, and we obtain the polynomial identity $P(X)=\prod_{j=1}^k(X+d_1+\cdots+d_j)$ .