第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}

が成り立つ。

ステップ 3/6: 数列は減少し得ない

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

ざっくり言うと

P は正の整数上で狭義単調増加なので、ステップ2の恒等式から、数列のどこか一箇所で減少が起きるとそれが伝播し、正の整数からなる終わりのない下降列を生んでしまうが、これは不可能である。

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

詳しい解説

$P$ は係数がすべて非負なので $\mathbb N$ 上で狭義単調増加である。ある $n$ で $a_n<a_{n-1}$ なら、ステップ2より $P(a_n)<P(a_{n-1})$ となり、 $a_{n+k}<a_n$ 、実際には $a_{n+k}<a_n<a_{n-1}$ が成り立つ。この議論を繰り返すと正の整数からなる無限の狭義減少列ができてしまい、不可能である。よって $a_1\le a_2\le\cdots$ である。もし等号 $a_n=a_{n-1}$ が起きたなら、ステップ2は $a_{n+k}=a_n$ を強制し、数列が非減少であることから $a_{n-1}=a_n=\cdots=a_{n+k}$ が強制され、下向きの帰納法により数列全体が定数となる。