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 6 of 6: The whole sequence is an arithmetic progression

Previous step Next step

In plain words

Once P is identified with this specific product, the output tuple of increments it forces is unique, so eventually the sequence must repeat the same increment forever, and induction backward shows it was always arithmetic.

a_n=a_1+(n-1)d\ \text{for all } n

Detailed analysis

There is a finite set of possible tuples, and for each tuple $e$ let $Q_e(X)=\prod_{j=1}^k(X+e_1+\cdots+e_j)$ . The tuple from Step 5 satisfies $Q_e=P$ . Every other tuple can occur only finitely often: otherwise the distinct values $a_n$ at those indices would give infinitely many roots of the nonzero polynomial $Q_e-P$ . Thus, for all sufficiently large $n$ , $\delta(n)=(d_1,\ldots,d_k)$ . Applying this also to $\delta(n+1)$ shows $(d_2,\ldots,d_k,a_{n+k+1}-a_{n+k})=(d_1,\ldots,d_k)$ , so $d_1=\cdots=d_k=:d$ and the tail is an arithmetic progression. Consequently $P(X)=F(X):=\prod_{j=1}^k(X+jd)$ . To extend the progression backwards, suppose $a_{n+1},\ldots,a_{n+k}$ already have common difference $d$ . Then $F(a_n)=P(a_n)=\prod_{j=1}^k(a_{n+1}+(j-1)d)=F(a_{n+1}-d)$ . The function $F(t)$ is strictly increasing for $t>-d$ , and both arguments lie in that interval, so $a_n=a_{n+1}-d$ . Downward induction reaches $n=1$ and proves $a_n=a_1+(n-1)d$ for every $n$ , with common difference $d$ .