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 3 of 6: The sequence cannot decrease

Previous step Next step

In plain words

Because P is strictly increasing on positive integers, the identity from Step 2 shows that a single decrease anywhere in the sequence would propagate into an endless descent of positive integers, which is impossible.

a_1\le a_2\le a_3\le\cdots\ \text{or the sequence is constant}

Detailed analysis

$P$ is strictly increasing on $\mathbb N$ since all its coefficients are non-negative. If $a_n<a_{n-1}$ for some $n$ , Step 2 gives $P(a_n)<P(a_{n-1})$ , so $a_{n+k}<a_n$ , and in fact $a_{n+k}<a_n<a_{n-1}$ ; repeating this argument produces an infinite strictly decreasing sequence of positive integers, which is impossible. Hence $a_1\le a_2\le\cdots$ . If equality $a_n=a_{n-1}$ ever occurs, Step 2 forces $a_{n+k}=a_n$ , and since the sequence is non-decreasing this forces $a_{n-1}=a_n=\cdots=a_{n+k}$ , and downward induction then makes the whole sequence constant.