MathLabs

第3题

对每个整数 k≥2k\ge2，求出所有满足下列条件的正整数无穷数列 a1,a2,…a_1,a_2,\ldots：存在一个形如 P(x)=xk+ck−1xk−1+⋯+c1x+c0P(x)=x^k+c_{k-1}x^{k-1}+\cdots+c_1x+c_0 的多项式 PP，其中 c0,c1,…,ck−1c_0,c_1,\ldots,c_{k-1} 是非负整数，使得对每个整数 n≥1n\ge1 都有 P(an)=an+1an+2⋯an+kP(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}。
第 4/6 步：增量是有界的
上一步下一步
通俗地说

由于 P(x) 增长速度只比 x^k 稍快一点，将 P(a_n) 与大于 a_n 的 k 个连续整数之积相比较，就可以看出下一项不能跳得太远。

an+1−an≤C for a constant Ca_{n+1}-a_n\le C\ \text{for a constant } C
详细分析

假设数列不是常数列。由第 3 步，数列此时严格递增，因此对每个 j≥1j\ge1 都有 an+j≥an+ja_{n+j}\ge a_n+j。令 C=1+c0+c1+⋯+ck−1C=1+c_0+c_1+\cdots+c_{k-1}。对每个整数 x≥1x\ge1，有 P(x)=xk+∑i=0k−1cixi≤xk+(C−1)xk−1<xk−1(x+C)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=anx=a_n，利用定义方程以及后面 k−1k-1 项的下界，得到 an+k=P(x)an+1⋯an+k−1<xk−1(x+C)(x+1)(x+2)⋯(x+k−1)<x+Ca_{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。由于 an+1≤an+ka_{n+1}\le a_{n+k}，故 an+1<an+Ca_{n+1}<a_n+C，所以每个整数增量 an+1−ana_{n+1}-a_n 至多为 C−1C-1（特别地被 CC 所界）。