第3题

对每个整数

k\ge2

，求出所有满足下列条件的正整数无穷数列

a_1,a_2,\ldots

：存在一个形如

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

的多项式

P

，其中

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)$ 。