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}。
第 3/6 步：数列不能递减
上一步下一步
通俗地说

由于 P 在正整数上严格递增，第 2 步中的恒等式表明，数列中任何一处出现的减少都会传播下去，形成正整数的无穷递减序列，而这是不可能的。

a1≤a2≤a3≤⋯ or the sequence is constanta_1\le a_2\le a_3\le\cdots\ \text{or the sequence is constant}
详细分析

由于 PP 的所有系数都非负，故在 N\mathbb N 上严格递增。若对某个 nn 有 an<an−1a_n<a_{n-1}，由第 2 步得 P(an)<P(an−1)P(a_n)<P(a_{n-1})，从而 an+k<ana_{n+k}<a_n，事实上 an+k<an<an−1a_{n+k}<a_n<a_{n-1}；重复这一论证会得到一个无穷的严格递减正整数序列，这是不可能的。因此 a1≤a2≤⋯a_1\le a_2\le\cdots。若某处出现等号 an=an−1a_n=a_{n-1}，第 2 步迫使 an+k=ana_{n+k}=a_n，又因数列不减，这就迫使 an−1=an=⋯=an+ka_{n-1}=a_n=\cdots=a_{n+k}，再由向下的归纳法可知整个数列都是常数。