具体数学-第14课（牛顿级数和生成函数）

原文链接：

具体数学-第14课 - WeiYang Blog

牛顿级数

多项式函数的一般表示形式为：

也可以将其表示为下降阶乘幂的形式：

这种表示的好处是，求差分更加方便：

因为有

所以多项式又可以表示为组合数的形式，也被叫做牛顿级数：

这种形式的差分也特别简单，因为有

所以 阶差分可以写为：

所以有：

所以牛顿级数又可以写为：

这个形式是不是很像泰勒展开？

生成函数

对于无限序列 ，定义它的生成函数为：

定义一个函数用来表示 的系数：

两个生成函数相乘的结果为：

考虑下面的二项展开：

可以发现这就是序列 的生成函数。
替换变量可以得到：

两个式子相乘可以得到：

等式两边 的系数相等，于是：

这和上节课讲到的范德蒙德卷积公式类似！这里是用生成函数证出来的。

同理根据

可以得到

下面是一个重要的生成函数：

它其实就是序列 的生成函数。

生成函数应用

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

例如大家很熟悉的斐波那契数列：

首先为了统一表示，将递归式改写为如下形式：

然后两边同时乘以 ，得到：

两边对指标 同时求和，可以得到：

所以

最后只要将 表示成多项式的形式就行了， 就是斐波那契数列的通项公式了。