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

が成り立つ。

ステップ 5/6: 増分のパターンに鳩の巣原理を使う

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

ざっくり言うと

増分が有界なので、ある添字以降の k 個の連続な差の組が取り得る値は有限個しかなく、したがってある組が無限回繰り返されるはずであり、無限回成り立つ多項式の恒等式は恒等的に成り立たなければならない。

(d_1,\ldots,d_k)\ \text{recurs}\implies P(X)=\prod_{j=1}^k(X+d_1+\cdots+d_j)

詳しい解説

非定数の場合、各 $n$ に対して $\delta(n)=(a_{n+1}-a_n,\ldots,a_{n+k}-a_{n+k-1})$ とおく。ステップ4により各成分は $\{1,2,\ldots,C-1\}$ に属するので、現れ得る組は有限個である。無限個の添字 $N$ で現れる組 $(d_1,\ldots,d_k)$ を一つ選ぶ。そのような各 $N$ について $s_j=d_1+\cdots+d_j$ とおけば、 $P(a_N)=\prod_{j=1}^k(a_N+s_j)$ である。数列は狭義単調増加なので $a_N$ は互いに異なる無限個の整数である。したがって、零多項式でない $P(X)-\prod_{j=1}^k(X+s_j)$ がそのすべてで消えることはなく、多項式恒等式 $P(X)=\prod_{j=1}^k(X+d_1+\cdots+d_j)$ を得る。