生成函数

生成函数（generating function）把一列数当作幂级数的系数。对数列 $a_{0}, a_{1}, \dots$ ，普通生成函数为 $A (z) = \sum_{n \geq 0} a_{n} z^{n}$ 。变量 $z$ 首先是记录下标的记号；需要代入具体数值时，还必须讨论级数是否收敛。生成函数让递推转成代数方程，再从系数读回原数列。

把斐波那契递推写成方程

设 $F_{0} = 0, F_{1} = 1$ 且 $F_{n} = F_{n - 1} + F_{n - 2}$ （ $n \geq 2$ ），令 $F (z) = \sum_{n \geq 0} F_{n} z^{n}$ 。对递推式按 $n \geq 2$ 求和，左边为 $F (z) - z$ ，右边两项分别为 $z F (z)$ 、 $z^{2} F (z)$ 。整理得到 $F (z) - z = z F (z) + z^{2} F (z), F (z) = \frac{z}{1 - z - z^{2}} .$ 分子中的 $z$ 来自初值 $F_{1} = 1$ ；漏掉初值会给出另一条数列。

系数运算的含义

若 $A (z) = \sum a_{n} z^{n}$ 、 $B (z) = \sum b_{n} z^{n}$ ，则乘积中 $z^{n}$ 的系数为 $\sum_{k = 0}^{n} a_{k} b_{n - k}$ 。这是把总大小 $n$ 分成两部分的所有方式逐项相加，所以柯西乘积和计数问题都可使用。对 $F (z)$ 的有理式展开，依次得到 $z + z^{2} + 2 z^{3} + 3 z^{4} + \dots$ ，与递推计算核对一致。形式幂级数的系数运算不要求先选一个收敛的 $z$ ；把它当数值函数使用才需要收敛范围。

参考资料

MIT，Mathematics for Computer Science，Generating Functions 章节。
MIT 6.042J Fall 2010，Mathematics for Computer Science 课程讲义。
继续阅读：递推关系、幂级数、柯西乘积。