牛顿级数

多项式函数的一般表示形式为：
<!–swig0–>
也可以将其表示为下降阶乘幂的形式：
<!–swig1–>
这种表示的好处是，求差分更加方便：
<!–swig2–>
因为有
<!–swig3–>
所以多项式又可以表示为组合数的形式，也被叫做牛顿级数：
<!–swig4–>
这种形式的差分也特别简单，因为有
<!–swig5–>
所以$n$阶差分可以写为：
<!–swig7–>
所以有：
<!–swig8–>
所以牛顿级数又可以写为：
<!–swig9–>
这个形式是不是很像泰勒展开？

生成函数

对于无限序列$\left\langle { {a_0},{a_1},{a_2}, \ldots } \right\rangle $，定义它的生成函数为：
<!–swig11–>
定义一个函数用来表示$z^n$的系数：
<!–swig13–>
两个生成函数相乘的结果为：
<!–swig14–>
考虑下面的二项展开：
<!–swig15–>
可以发现这就是序列$\left\langle {\left( {\begin{array}{\*{20}{c}}r\\0\end{array}} \right),\left( {\begin{array}{\*{20}{c}}r\\1\end{array}} \right),\left( {\begin{array}{\*{20}{c}}r\\2\end{array}} \right), \ldots } \right\rangle $的生成函数。
替换变量可以得到：
<!–swig17–>
两个式子相乘可以得到：
<!–swig18–>
等式两边$z^n$的系数相等，于是：
<!–swig20–>
这和上节课讲到的范德蒙德卷积公式类似！这里是用生成函数证出来的。

同理根据
<!–swig21–>
可以得到
<!–swig22–>
下面是一个重要的生成函数：
<!–swig23–>
它其实就是序列$\left\langle { {1},{1},{1}, \ldots } \right\rangle $的生成函数。

生成函数应用

那么生成函数有什么应用呢？一个很重要的应用就是用来求解递归式。

例如大家很熟悉的斐波那契数列：
<!–swig25–>

首先为了统一表示，将递归式改写为如下形式：
<!–swig26–>
然后两边同时乘以$z^n$，得到：
<!–swig28–>
两边对指标$n$同时求和，可以得到：
<!–swig30–>
所以
<!–swig31–>
最后只要将$\frac{z}{ {1 - z - {z^2}}}$表示成多项式的形式就行了，$[{z^n}]\frac{z}{ {1 - z - {z^2}}}$就是斐波那契数列的通项公式了。