用生成函数求数列通项公式

生成函数是对应于给定数列的一个形式级数，常见的生成函数有普通生成函数、指数型生成函数以及Dirichlet生成函数。

定义1

数列

​

的普通生成函数是下面的形式级数:

​

定义2

数列

​

的指数型生成函数是下面的形式级数:

​

定义3

数列

​

的Dirichlet生成函数是下面的形式级数:

​

用生成函数求数列通项公式

前面介绍过斐波那契数列，其递推公式为

​

根据递推公式，该数列的普通生成函数满足

​

即

​

根据上述方程解除f(x)，

​

裂项得到

​

根据无穷等比数列求和公式，或广义二项式定理，或泰勒中值定理，可以得到1/(1-x)(泰勒级数与幂级数)的幂级数展开式为

​

因此可以根据上式将上述f(x)的初等表达式括号中的两项分别展开为幂级数，然后次数相同项求差，再与括号外的常数相乘，便得到f(x)的幂级数展开式，其n次项系数为

上式就是斐波那契数列的通项公式。

    事实上一般的递推公式为线性形式的数列，都可以用生成函数法按照上述思路求出通项公式。