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 4 of 6: Increments are bounded

Previous step Next step

In plain words

Because P(x) grows only slightly faster than x^k, comparing P(a_n) to the product of k consecutive integers above a_n shows the next term cannot jump too far ahead.

a_{n+1}-a_n\le C\ \text{for a constant } C

Detailed analysis

Assume the sequence is non-constant. Step 3 then gives strict increase, so $a_{n+j}\ge a_n+j$ for every $j\ge1$ . Put $C=1+c_0+c_1+\cdots+c_{k-1}$ . For every integer $x\ge1$ , $P(x)=x^k+\sum_{i=0}^{k-1}c_i x^i\le x^k+(C-1)x^{k-1}<x^{k-1}(x+C)$ . Hence, with $x=a_n$ , the defining equation and the lower bounds for the first $k-1$ later terms give $a_{n+k}=\dfrac{P(x)}{a_{n+1}\cdots a_{n+k-1}}<\dfrac{x^{k-1}(x+C)}{(x+1)(x+2)\cdots(x+k-1)}<x+C$ . Since $a_{n+1}\le a_{n+k}$ , we get $a_{n+1}<a_n+C$ , so every integer increment $a_{n+1}-a_n$ is at most $C-1$ (and in particular is bounded by $C$ ).