对于递推式为多项式的证明

考虑证明一个式子为多项式

若记 \(G(x)\) 为一个多项式（注意：此处要求是一个连续多项式，不能分段） \[ \Delta F(x)=G(x) \]

我们可以证明此为其的充要条件，证明如下： 充分性

则有我们可以将多项式化成下降幂的形式，根据我们对于差分算子的定义，我们很轻松的就得到了 \[ \sum_{x_0}^x x^{\underline{a}} = \cfrac{1}{a+1}(x^{\underline{a+1}} - (x_0-1)^{\underline{a+1}}) \] 则我们证明了 \[ \sum_{x_0}^xG(x) \] 为一个多项式

则我们有 \[ F(x) = \sum_{x_0}^xG(x) + F(x_0-1) \] 得证

必要性：

我们考察对于任意多项式 \(F(x)\) 则 \(F(x) - F(x-1)\) 显然为一个多项式,其次数比原多项式少 \(1\)

以上方式还可以通过多项式的加法后系数不变等性质进行推倒。

总的说来，当一个递推式中只出现和式，积式，常数乘法，常数加法，函数复合时我们可以认定其是一个多项式

式子总结

• \(\deg (f + g)=\max(\deg f, \deg g)\)
• \(\deg (f \circ g)= \deg f \deg g\)
• \(\deg \sum_{i=x_0}^x f(x)=\deg f(x) + 1\)

利用这三条式子的组合，我们可以得到式子的次数，以更好的解题。