天不为人之恶寒也辍冬，地不为人之恶辽远也辍广，君子不为小人之匈匈也辍行。

# 母函数的基本知识

母函数方法是指通过将数列各项作为某一级数的系数 (或系数的一部分)，采用函数变换的思想，求解数列通项等信息的方法。其中的某一级数对应的函数就称为母函数，或称生成函数 (generating function)。母函数最常用来解决的问题就是数列的通项问题和组合计数问题。

母函数一般可以分为两类。第一类为普通型母函数，即$\displaystyle G(x) = \sum_{i=0}^\infty a_ix^i$；第二类称为指数型母函数，即$\displaystyle G_e(x) = \sum_{i=0}^\infty \frac{a_i}{i!}x^i$。

在对母函数进行级数展开和变形时，大多采用泰勒公式即可。我们一般不需要考虑级数的敛散性，而是按照正常的级数展开规则进行计算。换句话说，我们是在对延拓的级数进行计算。

# 母函数的应用

# 求解递推数列通项

# 齐次关系的情形

例题 1 求解斐波那契数列的通项。

解构造母函数$\displaystyle F(x) = \sum_{i=0}^\infty F_ix^i$，则$\displaystyle F(x) = F_0 + F_1x + \sum_{i=0}^\infty (F_{i+1} + F_i)x^{i+2} = 1 + xF(x) + x^2F(x)$，故$F(x) = \frac{1}{1-x-x^2} = \frac{1}{\sqrt 5}\left(\frac{1}{\frac{-1+\sqrt 5}{2} - x} + \frac{1}{\frac{1+\sqrt 5}{2}+ x}\right) = \frac{1}{\sqrt{5}}\left(\sum_{i=0}^\infty \left(\frac{1+\sqrt{5}}{2}\right)^{i+1}x^i - \sum_{i=0}^\infty \left(\frac{1-\sqrt{5}}{2}\right)^{i+1}x^i\right)$。根据母函数的构造方式，得到$F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)$。

根据上面的题目，我们容易发现，母函数的求法相对于特征方程的求解更加繁琐，但是可以更好的解释为什么这样求解的问题。但在一般的计算中，还是采用特征方程更为快捷。

如果希望加快效率，我们可以总结出几个较基本的公式：

1.$\displaystyle \frac{1}{1-px} = \sum_{i=0}^\infty (px)^i$
2.$\displaystyle \frac{1}{p-x} = \sum_{i=0}^\infty \frac{x^i}{p^{i+1}}$
3.$\displaystyle \frac{1}{1+px} = \sum_{i=0}^\infty (-px)^i$
4.$\displaystyle \frac{1}{p+x} = -\sum_{i=0}^\infty \frac{x^i}{(-p)^{i+1}}$

这些公式虽然看上去比较愚蠢，但是可以使计算更加快捷。

# 非齐次关系的情形

例题 2 求$a_n-a_{n-1}-6a_{n-2} = 3^n$ 的通项公式，其中$a_0 = 5$，$a_i = 2$。
解构造母函数$\displaystyle G(x)=\sum_{i=0}^na_ix^i$。则将$a_n-a_{n-1}-6a_{n-2} = 3^n$ 两侧同乘$x^n$ 再相加，得到$G(x)-xG(x)-6x^2G(x) = \frac{1}{1-3x}$。分拆后进行泰勒展开易求。