生成函数
对于无限序列 
，定义它的生成函数为：
定义一个函数用来表示 
的系数：
两个生成函数相乘的结果为：
考虑下面的二项展开：
可以发现这就是序列 
的生成函数。
替换变量可以得到：
两个式子相乘可以得到：
等式两边 
的系数相等，于是：
这和上节课讲到的范德蒙德卷积公式类似！这里是用生成函数证出来的。
同理根据
可以得到
下面是一个重要的生成函数：
它其实就是序列 
的生成函数。
生成函数应用
那么生成函数有什么应用呢？一个很重要的应用就是用来求解递归式。
例如大家很熟悉的斐波那契数列：
首先为了统一表示，将递归式改写为如下形式：
然后两边同时乘以 
，得到：
两边对指标 n 同时求和，可以得到：
所以
最后只要将 
表示成多项式的形式就行了， 
就是斐波那契数列的通项公式了。
