第3問

各整数

k\ge2

に対して、次を満たす多項式

P

が存在するような正整数の無限数列

a_1,a_2,\ldots

をすべて決定せよ：

P(x)=x^k+c_{k-1}x^{k-1}+\cdots+c_1x+c_0

の形をしており、

c_0,c_1,\ldots,c_{k-1}

は非負整数であって、すべての整数

n\ge1

に対して

P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}

が成り立つ。

ステップ 4/6: 増分は有界である

前のステップ次のステップ

ざっくり言うと

P(x) は x^k よりわずかに速く増加するだけなので、P(a_n) を a_n より大きい k 個の連続な整数の積と比較すると、次の項があまり遠くまで跳べないことが分かる。

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

詳しい解説

数列が定数でないと仮定する。このときステップ3より数列は狭義単調増加なので、任意の $j\ge1$ について $a_{n+j}\ge a_n+j$ である。 $C=1+c_0+c_1+\cdots+c_{k-1}$ とおく。任意の整数 $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)$ である。したがって $x=a_n$ とし、定義式と後の $k-1$ 項に対する下界を使うと、 $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$ を得る。 $a_{n+1}\le a_{n+k}$ だから $a_{n+1}<a_n+C$ であり、各整数の増分 $a_{n+1}-a_n$ は高々 $C-1$ （したがって特に $C$ ）である。