形式幂级数的运算、性质、应用

摘要: 全面梳理形式幂级数的理论和应用

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 数学分析-级数论 中，我们系统学习过函数项级数，首先是收敛性、收敛半径以及各种判别法，然后是和函数和极限函数关于连续、可积、可微的性质，接着就到了幂级数及其收敛相关的性质，接着讨论了函数的幂级数展开，包括泰勒级数和麦克劳林级数，拉格朗日余项与柯西余项。

在组合数学以及概率中，我们还了解过母函数这个概念，并且解决了组合数学和概率中的很多问题，比如 组合数学2-母函数,递推关系、一段时间内事件发生次数，泊松分布。

这两个概念在形式上都是 $f(x) = \sum\limits_{i=0}\limits^{\infty}a_{i}x^{i}$，但是其本质完全不同。分析学中关心的级数 $\sum\limits_{i=0}\limits^{\infty}a_{i}x^{i}$ 的收敛性，以及函数 $f(x)$ 的连续、可微、图像等性质，在组合学中的母函数中不考虑；而在母函数的推导中我们又可以参考分析学中关于函数的麦克劳林级数展开的一些结论，藕断丝连。本文我们就系统介绍一下母函数与形式幂级数的基础理论，以及常见的应用场景。

母函数的提出

对于给定的数列 $\{a_{k}\}, k=0,1,\cdots,n$，如果它恰好是某个多项式 $p(\vec{x})$ 的系数，即：

$$p(\vec{x}) = a_{0} + a_{1}x + a_{2}x^{2} + \cdots + a_{n}x^{n}$$

那么称 $p(\vec{x})$ 称为该数列的母函数或生成函数。

所谓生成函数，可以理解为 数列 $\{a_{k}\}, k=0,1,\cdots,n$ 是由多项式 $p(\vec{x})$ 产生的。

例如二项式定理，$(1 + x)^{n} = \sum\limits_{i=0}\limits^{n}\binom{n}{i}x^{i}$，该公式我们可以理解为数列 $\binom{n}{0}, \binom{n}{1}, \cdots, \binom{n}{n}$ 的母函数为 $(1+x)^{n}$。

如果数列是无穷数列，那么其母函数就是一个无穷次多项式：

$$\sum\limits_{i=0}\limits^{\infty}a_{i}x^{i} = a_{0} + a_{1}x + a_{2}x^{2} + \cdots + a_{n}x^{n} + \cdots$$

这种无穷次多项式称为形式幂级数。

该级数在形式上相当于分析学中的幂级数 $\sum\limits_{i=0}\limits^{\infty}a_{i}(x-x_{0})^{i}$ 在 $x_{0}=0$ 时的情况。但是在这里我们不讨论其收敛性等问题，而是把整个幂级数看做一个对象进行研究，类似于把 $a+bi$ 看成一个称为复数的整体来研究，因此称其为形式幂级数。

母函数的运算

当把形式幂级数作为整体视为新的研究对象，那么其运算就要重新定义了。

形式级数的系数在域 F 中，称其为域 F 上的形式级数。域 F 上所有形式级数的集合记为 $F[[x]]$，$F[[x]]$ 在形式级数的加法和乘法下构成一个环。

如果母函数是有限项的，那么对应有限项的数列，可以理解为某一项之后均为 0，此时形式幂级数是一个多项式。

记 $[x^{n}]f(x)$ 表示 $f(x)$ 中 $x^{n}$ 的系数，用 $\{a_{n}\}_{n=0}^{\infty} \leftrightarrow f(x)$ 表示数列和生成函数的关系。

$$f(x) = \sum\limits_{n=0}\limits^{\infty}a_{n}x^{n} \\ \Updownarrow \\ a_{n} = [x^{n}]f(x) \\ \Updownarrow \\ \{a_{n}\}_{n=0}^{\infty} \leftrightarrow f(x) \\$$

相等(数列与母函数一一对应)

两个形式幂级数 $\sum\limits_{i=0}\limits^{\infty}a_{i}x^{i}$，$\sum\limits_{i=0}\limits^{\infty}b_{i}x^{i}$。

当且仅当 $a_{i}=b_{i}, i=0,1,2, \cdots$ 时，才认为两个形式幂级数相等。

因此数列 $\{a_{n}\}$ 与其母函数之间是一一对应的。

加法

两个形式幂级数 $\sum\limits_{i=0}\limits^{\infty}a_{i}x^{i}$，$\sum\limits_{i=0}\limits^{\infty}b_{i}x^{i}$。

它们的和是一个以 $\{a_{i}+b_{i}\}$ 为系数的形式幂级数，即：

$$\sum\limits_{i=0}\limits^{\infty}a_{i}x^{i} + \sum\limits_{i=0}\limits^{\infty}b_{i}x^{i} = \sum\limits_{i=0}\limits^{\infty}(a_{i} + b_{i})x^{i}$$

数乘

常数 $\alpha$ 和形式幂级数 $\sum\limits_{n=0}\limits^{\infty}a_{n}x^{n}$ 的乘积为以 $\{\alpha a_{n}\}$ 为系数的形式幂级数：

$$\alpha\sum\limits_{n=0}\limits^{\infty}a_{n}x^{n} = \sum\limits_{n=0}\limits^{\infty}(\alpha a_{n})x^{n}$$

乘法

两个形式幂级数 $\sum\limits_{i=0}\limits^{\infty}a_{i}x^{i}$，$\sum\limits_{i=0}\limits^{\infty}b_{i}x^{i}$。

它们的和是一个以 $\{c_{i}\}$ 为系数的形式幂级数，$c_{n} = \sum\limits_{k=0}\limits^{n}a_{k}b_{n-k}$，即：

$$(\sum\limits_{n=0}\limits^{\infty}a_{n}x^{n})(\sum\limits_{n=0}\limits^{\infty}b_{n}x^{n}) = \sum\limits_{n=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{n}a_{k}b_{n-k})x^{n}$$

形式幂级数的乘法可以视为多项式乘法的推广。

例：$(\sum\limits_{n=0}\limits^{\infty}x^{n})^{2}$

令 $\sum\limits_{n=0}\limits^{\infty}a_{n}x^{n}$，$\sum\limits_{n=0}\limits^{\infty}b_{n}x^{n}$，其中 $a_{n} = b_{n} = 1$，因此 $c_{n} = \sum\limits_{k=0}\limits^{n}a_{k}b_{n-k} = n + 1$。

因此 $(\sum\limits_{n=0}\limits^{\infty}x^{n})^{2} = \sum\limits_{n=0}\limits^{\infty}(n+1)x^{n}$。

例：$(\sum\limits_{n=0}\limits^{\infty}a_{n}x^{n})(\sum\limits_{n=0}\limits^{\infty}x^{n})$

令 $\sum\limits_{n=0}\limits^{\infty}b_{n}x^{n} = \sum\limits_{n=0}\limits^{\infty}x^{n}$，其中 $b_{n} = 1$，于是 $c_{n} = \sum\limits_{k=0}\limits^{n}a_{k}b_{n-k} = \sum\limits_{k=0}\limits^{n}a_{k}$。

因此 $(\sum\limits_{n=0}\limits^{\infty}a_{n}x^{n})(\sum\limits_{n=0}\limits^{\infty}x^{n}) = \sum\limits_{n=0}\limits^{\infty}(\sum\limits_{i=0}\limits^{n}a_{i})x^{n}$

前缀和数列的母函数

由上面的例子，如果数列 $\{a_{0}, a_{1}, \cdots, a_{n}\}$ 的母函数为 $f(x)$，那么前缀和数列 $\{sums_{0}, sums_{1}, \cdots, sums_{n}\}$，其中 $sums_{i} = \sum\limits_{j=0}\limits^{i}a_{j}$。其母函数为：

$$f(x)\sum\limits_{n=0}\limits^{\infty}x^{n} = \frac{f(x)}{1 - x}$$

除法

三个形式幂级数 $f = \sum\limits_{i=0}\limits^{\infty}a_{i}x^{i}$，$g = \sum\limits_{i=0}\limits^{\infty}b_{i}x^{i}$，$h = \sum\limits_{i=0}\limits^{\infty}c_{i}x^{i}$。

如果 $f = gh$，则称 $f$ 被 $g$ 除的商为 $h$，记为 $\frac{f}{g} = h$。

形式幂级数的除法可以视为多项式除法的推广。

将 $f = gh$ 展开，

$\sum\limits_{i=0}\limits^{\infty}a_{i}x^{i} = (\sum\limits_{i=0}\limits^{\infty}b_{i}x^{i})(\sum\limits_{i=0}\limits^{\infty}c_{i}x^{i}) = \sum\limits_{n=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{n}b_{k}c_{n-k})x^{n}$，因此：

$$a_{n} = \sum\limits_{k=0}\limits^{n}b_{k}c_{n-k} \\ \Rightarrow c_{n} = \frac{a_{n} - \sum\limits_{k=1}\limits^{n}b_{k}c_{n-k}}{b_{0}}$$

如果 $b_{0}=0$ 而 $a_{0}\neq 0$，此时不论 $C_{0}$ 如何取值都不能使 $a_{0} = b_{0}c_{0}$，因此不是任意两个形式幂级数都可以相除，这与两个多项式的相除的情况一样。

例：$\sum\limits_{n=0}\limits^{\infty}x^{n} = \frac{1}{1-x}$

将 1 和 $1 - x$ 都视为形式幂级数，则它们的商如下：

$$\frac{1}{1-x} = \sum\limits_{n=0}\limits^{\infty}c_{n}x^{n} \\ \begin{align} \Rightarrow 1 = (1 - x)\sum\limits_{n=0}\limits^{\infty}c_{n}x^{n} &= \sum\limits_{n=0}\limits^{\infty}c_{n}x^{n} - \sum\limits_{n=0}\limits^{\infty}c_{n}x^{n+1} \\ &= \sum\limits_{n=0}\limits^{\infty}c_{n}x^{n} - \sum\limits_{n=1}\limits^{\infty}c_{n-1}x^{n} \\ &= c_{0} + \sum\limits_{n=1}\limits^{\infty}(c_{n} - c_{n-1})x^{n} \\ \end{align}$$

对比两边同幂次的系数，得到：

$$c_{0} = 1, c_{n} - c_{n-1} = 0, n = 1,2,3,\cdots$$

因此：

$$\frac{1}{1-x} = 1 + x + x^{2} + \cdots + x^{n} + \cdots$$

注意：上式的相等指的是形式幂级数的相等，两边不能用具体的 x 值代入。

例：$\sum\limits_{n=0}\limits^{\infty}(rx)^{n} = \frac{1}{1-rx}$

将 1 和 $1 - rx$ 都视为形式幂级数：

$$1 = \sum\limits_{n=0}\limits^{\infty}a_{n}x^{n} \\ 1 - rx = \sum\limits_{n=0}\limits^{\infty}b_{n}x^{n} \\$$

由此得：

$$a_{0} = 1, a_{1} = a_{2} = \cdots = a_{n} = \cdots = 0 \\ b_{0} = 1, b_{1} = -r, b_{2} = b_{3} = \cdots = b_{n} = \cdots = 0 \\$$

由形式幂级数商 $\sum\limits_{n=0}\limits^{\infty}c_{n}x^{n}$ 的定义，有：

$$c_{i} = \frac{a_{i} - \sum\limits_{k=1}\limits^{i}b_{k}c_{i-k}}{b_{0}} = r^{i}$$

因此展开式如下：

$$\frac{1}{1-rx} = 1 + rx + r^{2}x^{2} + \cdots r^{n}x^{n} + \cdots$$

在 $\frac{1}{1-x} = 1 + x + x^{2} + \cdots + x^{n} + \cdots$ 中用 x 代替 rx 也是可以的。

例：$\frac{1}{(1-x)^{n+1}} = \sum\limits_{k=0}\limits^{\infty}\binom{n+k}{n}x^{k}$

对 n 用数学归纳法，n = 1 时，$\frac{1}{(1-x)} = 1 + x + x^{2} + \cdots$ 成立。

假设 n 时成立 $\frac{1}{(1-x)^{n}} = \sum\limits_{k=0}\limits^{\infty}\binom{n-1+k}{n-1}x^{k}$，下面考虑 $n+1$ 的情况。

$$\begin{align} \frac{1}{(1-x)^{n+1}} &= \frac{1}{(1-x)^{n}}\frac{1}{1-x} \\ &= (\sum\limits_{i=0}\limits^{\infty}\binom{n+i-1}{n-1}x^{i})(\sum\limits_{i=0}\limits^{\infty}x^{i}) \\ &= \sum\limits_{i=0}\limits^{\infty}(\sum\limits_{j=0}\limits^{i}\binom{n+j-1}{n-1})x^{i} \\ \end{align}$$

由朱世杰恒等式 $\binom{n + m + 1}{n + 1} = \sum\limits_{i=0}\limits^{m}\binom{n+i}{n}$，得：

$$\begin{align} \frac{1}{(1-x)^{n+1}} &= \sum\limits_{i=0}\limits^{\infty}(\sum\limits_{j=0}\limits^{i}\binom{n-j-1}{n-1})x^{i} \\ &= \sum\limits_{i=0}\limits^{\infty}\binom{n+i}{n}x^{i} \\ \end{align}$$

这就证明了 $n + 1$ 的情况也成立。

平方根

两个形式幂级数 $f = \sum\limits_{i=0}\limits^{\infty}a_{i}x^{i}, a_{0} > 0$，$g = \sum\limits_{i=0}\limits^{\infty}b_{i}x^{i}, b_{0} > 0$。

如果 $f^{2} = g$，称 $f$ 是 $g$ 的平方根，记为 $f = \sqrt{g}$

例：$\sqrt{1+x} = 1 + \sum\limits_{n=1}\limits^{\infty}\frac{(-1)^{n-1}}{n2^{2n-1}}\binom{2n-2}{n-1}x^{n}$

记 $a_{0} = 1, a_{n} = \frac{(-1)^{n-1}}{n2^{2n-1}}\binom{2n-2}{n-1}$，那么原式写为 $\sqrt{1 + x} = \sum\limits_{n=0}\limits^{\infty}a_{n}x^{n}$。

因此只需要证明 $(\sum\limits_{n=0}\limits^{\infty}a_{n}x^{n})^{2} = 1 + x$。

由乘法的定义：

$$(\sum\limits_{n=0}\limits^{\infty}a_{n}x^{n})^{2} = \sum\limits_{n=0}\limits^{\infty}d_{n}x^{n} \\ d_{n} = \sum\limits_{k=0}\limits^{n}a_{k}a_{n-k}$$

可以看到 $d_{0} = a_{0}^{2} = 1$ 成立，$d_{1} = a_{0}a_{1} + a_{1}a_{0} = \frac{1}{2} + \frac{1}{2} = 1$ 成立，此时只需要证明 $n \geq 2$ 时 $d_{n} = 0$ 即可。

$$\begin{align} d_{n} &= \sum\limits_{k=0}\limits^{n}a_{k}a_{n-k} \\ &= 2a_{n} + \sum\limits_{k=1}\limits^{n-1}a_{k}a_{n-k} \\ &= \frac{(-1)^{n-1}}{n2^{2n-2}}\binom{2n-2}{n-1} \\ &\quad\quad + \sum\limits_{k=1}\limits^{k-1}\frac{(-1)^{k-1}}{k2^{2k-1}}\binom{2k-2}{k-1}\frac{(-1)^{n-k-1}}{(n-k)2^{2(n-k)-1}}\binom{2(n-k)-2}{n-k-1}\\ &= \frac{(-1)^{n-1}}{2^{2n-2}}(\frac{1}{n}\binom{2(n-1)}{n-1} - \sum\limits_{k=1}\limits^{n-1}\frac{1}{k(n-k)}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1}) \\ \end{align}$$

由以下组合恒等式，可得 $d_{n} = 0$，因此原公式得证。

$$\sum\limits_{k=1}\limits^{n-1}\frac{1}{k(n-k)}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} = \frac{1}{n}\binom{2(n-1)}{n-1}, n=2,3,\cdots$$

以上组合恒等式的证明过程是通过基本恒等式加上归纳的方式，具体过程看文章 组合恒等式-基于六个基本组合恒等式。

例：$\sqrt{1-4x} = \sum\limits_{n=0}\limits^{\infty}\binom{2n}{n}x^{n}$

在上面的 $\sqrt{1+x}$ 中，用 $-4x$ 代替 $x$，得到：

$$\sqrt{1-4x} = 1 - \sum\limits_{k=1}\limits^{\infty}\frac{2}{k}\binom{2(k-1)}{k-1}x^{k}$$

记 $a_{0} = 1$, $a_{k} = -\frac{2}{k}\binom{2(k-1)}{k-1}$、$b_{k} = \binom{2k}{k}$，则只需要证明 $(\sum\limits_{k=0}\limits^{\infty}a_{k}x^{k})(\sum\limits_{k=0}\limits^{\infty}b_{k}x^{k}) = 1$，则根据母函数除法的定义，原等式成立。

记 $d_{n} = \sum\limits_{k=0}\limits^{n}a_{k}b_{n-k}$，可以验证 $d_{0} = a_{0}b_{0} = 1$，剩下要证的是 $d_{n} = \sum\limits_{k=0}\limits^{n}a_{k}b_{n-k} = 0$。

$$\begin{align} d_{n} &= a_{0}b_{n} + \sum\limits_{k=1}\limits^{n-1}a_{k}b_{n-k} + a_{n}b_{0} \\ &= \binom{2n}{n} + \sum\limits_{k=1}\limits^{n-1}-\frac{2}{k}\binom{2k-2}{k-1}\binom{2(n-k)}{n-k} - \frac{2}{n}\binom{2(n-1)}{n-1} \end{align}$$

要证 $d_{n} = 0$，即证以下等式：

$$\sum\limits_{k=1}\limits^{n-1}\frac{1}{k}\binom{2k-2}{k-1}\binom{2(n-k)}{n-k} = \frac{1}{2}\binom{2n}{n} - \frac{1}{n}\binom{2(n-1)}{n-1} = 2(1-\frac{1}{n})\binom{2(n-1)}{n-1}$$

由于 $\binom{2(n-k)}{n-k} = 2(2-\frac{1}{n-k})\binom{2(n-k-1)}{n-k-1}$，上式左端写为：

$$\begin{align} & \sum\limits_{k=1}\limits^{n-1}\frac{1}{k}\binom{2k-2}{k-1}\binom{2(n-k)}{n-k} \\ = &4\sum\limits_{k=1}\limits^{n-1}\frac{1}{k}\binom{2k-2}{k-1}\binom{2(n-k-1)}{n-k-1} - 2\sum\limits_{k=1}\limits^{n-1}\frac{1}{k(n-k)}\binom{2k-2}{k-1}\binom{2(n-k-1)}{n-k-1} \\ = &2\binom{2n-2}{n-1} - \frac{2}{n}\binom{2n-2}{n-1} \end{align}$$

上式最后一步用到了组合恒等式结论，参考文章 组合恒等式-基于六个基本组合恒等式。

形式导数

$f(x) = \sum\limits_{n=0}\limits^{\infty}a_{n}x^{n}$，则 $f(x)$ 的形式导数如下：

$$f'(x) = \sum\limits_{n=0}\limits^{\infty}(n+1)a_{n+1}x^{n}$$

复合

$f(x) = \sum\limits_{n=0}\limits^{\infty}a_{n}x^{n}$，$g(x) = \sum\limits_{n=0}\limits^{\infty}b_{n}x^{n}$，满足 $b_{0} = 0$，可以定义复合：

$$f(g(x)) = \sum\limits_{n=0}\limits^{\infty}a_{n}(g(x))^{n}$$

当复合 $f(g(x))$ 和 $g(f(x))$ 均存在且 $f(g(x)) = g(f(x)) = x$ 时，称 $g(x)$ 为 $f(g(x))$ 的复合逆。

母函数的性质

基于 $\{a_{n}\}_{n=0}^{\infty}$ 的母函数为 $f(x) = \sum\limits_{n=0}\limits^{\infty}a_{n}x^{n}$，下面不加证明地给出一些常用的结论。

(1) $\{a_{n+1}\}_{n=0}^{\infty}$

$\{a_{n+1}\}_{n=0}^{\infty}$ 的母函数为 $\frac{f(x) - a_{0}}{x}$

(2) $\{a_{n+2}\}_{n=0}^{\infty}$

$\{a_{n+2}\}_{n=0}^{\infty}$ 的母函数为 $\frac{f(x) - a_{0} - a_{1}x}{x^{2}}$

(3) $\{a_{n+k}\}_{n=0}^{\infty}$

$\{a_{n+k}\}_{n=0}^{\infty}$ 的母函数为 $\frac{f(x) - a_{0} - a_{1}x - \cdots - a_{k-1}x^{k-1}}{x^{k}}$

(4) $\{na_{n}\}_{n=0}^{\infty}$

$\{na_{n}\}_{n=0}^{\infty}$ 的母函数为 $x\frac{\mathrm{d}}{\mathrm{d}x}f(x)$

$\{n\}_{n=0}^{\infty}$

推论：$\{n\}_{n=0}^{\infty} \leftrightarrow x\frac{\mathrm{d}}{\mathrm{d}x}\frac{1}{1-x} = \frac{x}{(1-x)^{2}}$

(5) $\{n^{k}a_{n}\}_{n=0}^{\infty}$

$\{n^{k}a_{n}\}_{n=0}^{\infty}$ 的母函数为 $(x\frac{\mathrm{d}}{\mathrm{d}x})^{k}f(x) = (x\frac{\mathrm{d}}{\mathrm{d}x})((x\frac{\mathrm{d}}{\mathrm{d}x})^{k-1}f(x))$

(6) $\{P(n)a_{n}\}_{n=0}^{\infty}$, $P$ 是任一多项式

$P$ 是任一多项式，$\{P(n)a_{n}\}_{n=0}^{\infty}$ 的母函数为 $P(x\frac{\mathrm{d}}{\mathrm{d}x})f(x)$

(7) $f(x)g(x)$

$\{b_{n}\}_{n=0}^{\infty}$ 的母函数为 $f(x) = \sum\limits_{n=0}\limits^{\infty}b_{n}x^{n}$，则 $f(x)g(x)$ 是 $\{\sum\limits_{k=0}\limits^{n}a_{k}b_{n-k}\}_{n=0}^{\infty}$ 的母函数。

(8) $(f(x))^{k}$

$(f(x))^{k}$ 是数列 $\{\sum\limits_{n_{1} + n_{2} + \cdots + n_{k} = n}a_{n_{1}}a_{n_{2}}\cdots a_{n_{k}}\}_{n=0}^{\infty}$ 的母函数。

$\{\sum\limits_{j=0}\limits^{n}a_{j}\}_{n=0}^{\infty}$

推论：$\frac{f(x)}{1-x}$ 是前缀和数列 $\{\sum\limits_{j=0}\limits^{n}a_{j}\}_{n=0}^{\infty}$ 的母函数。

---

应用

下面是母函数在各个场景中的应用，每个例子都很经典。

组合计数

(1) 不定方程非负整数解个数

对正整数 $k$，求 $x_{1} + x_{2} + \cdots + x_{k} = n$ 的非负整数解个数。

记 $a_{n}$ 为 $x_{1} + x_{2} + \cdots + x_{k} = n$ 的非负整数解个数，其生成函数为 $f(x)$。

$$\begin{align} f(x) &= \underbrace{(1 + x + x^{2} + \cdots)(1 + x + x^{2} + \cdots)\cdots(1 + x + x^{2} + \cdots)}_{k个} \\ &= (\sum\limits_{i=0}\limits^{\infty}x^{i})^{k} \\ &= \frac{1}{(1-x)^{k}} \\ \end{align}$$

考察 $f(x)$ 的 $x^{n}$ 的系数，得到：

$$a_{n} = [x^{n}]\frac{1}{(1-x)^{k}} = \binom{n+k-1}{n}$$

(2) 正整数 n 写成 k 个非负整数有序和

$\{1\}_{n=0}^{\infty}$ 的母函数为 $\frac{1}{1-x}$

因此 $\frac{1}{(1-x)^{k}}$ 是数列 $\{\sum\limits_{n_{1} + n_{2} + \cdots + n_{k} = n}a_{n_{1}}a_{n_{2}}\cdots a_{n_{k}}\}_{n=0}^{\infty}$ 的母函数。

我们要求的数列是 $\{f(n, k)\}$ ：

$$f(n, k) = [x^{n}]\frac{1}{(1-x)^{k}} = \binom{n+k-1}{n}$$

---

求和

$\sum\limits_{n=0}\limits^{\infty}\frac{n^{2} + 4n + 5}{n!}$

构造母函数：

$$e^{x} = \sum\limits_{n=0}\limits^{\infty}\frac{1}{n!}x^{n}$$

由母函数的性质：

$$\begin{align} \sum\limits_{n=0}\limits^{\infty}\frac{n^{2}+4n+5}{n!}x^{n} &= ((x\frac{\mathrm{d}}{\mathrm{d}x})^{2} + 4(x\frac{\mathrm{d}}{\mathrm{d}x}) + 5)e^{x} \\ &= (x^{2} + 5x + 5)e^{x} \\ \end{align}$$

令 $x=1$ 有：

$$\sum\limits_{n=0}\limits^{\infty}\frac{n^{2} + 4n + 5}{n!} = 11e$$

调和级数 $\sum\limits_{i=1}\limits^{n}\frac{1}{i}, n\geq 1$

记 $\{\frac{1}{n}\}_{n=1}^{\infty}$ 的母函数为 $f(x) = \sum\limits_{n=1}\limits^{\infty}\frac{x^{n}}{n}$。记 $a_{n} = \sum\limits_{i=1}\limits^{n}\frac{1}{i}$，其母函数为 $h(x)$，

由母函数的性质，有 $h(x) = \frac{f(x)}{1-x}$。

$f’(x) = \sum\limits_{i=1}\limits^{\infty}x^{n-1} = \frac{1}{1-x}$，于是可以得到 $f(x) = -\ln{(1-x)}$

因此：

$$\sum\limits_{n=0}\limits^{\infty}a_{n}x^{n} = - \frac{\ln{(1-x)}}{1-x} = \frac{1}{1-x}\ln{\frac{1}{1-x}}$$

---

证明组合恒等式

应用母函数来证明组合恒等式的基本思想是证明恒等式两端的数列具有相同的母函数。

另一种思想是把恒等式的某一端看成一个数列 $\{a_{n}\}$，然后算出其母函数 $f(x)$，再将 $f(x)$ 展开成幂级数（综合使用麦克劳林级数的结论以及形式幂级数的性质），其 $x^{n}$ 的系数就是 $a_{n}$ 的值。

执行以上思想的难点是构造合适的母函数，或者找到等式一边的母函数。

Vandermonde 恒等式

当 $n, m \geq 0$，有：

$$\binom{m+n}{k} = \sum\limits_{i=0}\limits^{k}\binom{m}{i}\binom{n}{k-i}$$

在 Vandermonde 恒等式中令 $m=n=k$ 有：

$$\sum\limits_{i=0}\limits^{n}\binom{n}{i}^{2} = \binom{2n}{n}$$

范德蒙德恒等式的具有把 $\binom{n+m}{q}$ 分解为和式的作用，在一些恒等式中很有用。

组合计数

$\binom{m+n}{k}$ 是 (m+n)-集合 $A \cup B$ 中 k-子集的个数，这里 $A = \{1,2,\cdots,m\}$, $B = \{m+1,m+2,\cdots,m+n\}$。

其中包含 A 的 i 个元素的 k-子集个数为 $\binom{m}{i}\binom{n}{k-i}$，因此和式 $\sum\limits_{i=0}\limits^{m}\binom{m}{i}\binom{n}{k-i}$ 正是对所有的 i 来计数这些子集的个数。也就是：

$$\binom{m+n}{k} = \sum\limits_{i=0}\limits^{k}\binom{m}{i}\binom{n}{k-i}$$

比较系数法

因为 $\binom{n}{k}$ 和 $\binom{m}{k}$ 的母函数分别为 $(1+x)^{n}$ 和 $(1+x)^{m}$。而 $\sum\limits_{k=0}\limits^{q}\binom{n}{k}\binom{m}{q-k}$ 是两个母函数乘积 $(1+x)^{n}(1+x)^{m} = (1+x)^{m+n}$ 的 $x^{q}$ 的系数，也就是 $\binom{m+n}{q}$。于是有：

$$\sum\limits_{k=0}\limits^{q}\binom{n}{k}\binom{n}{q-k} = \binom{m+n}{q}$$

判断母函数相等

构造两个形式幂级数：

$$(1 + x)^{n} = \sum\limits_{i=0}\limits^{\infty}\binom{n}{i}x^{i} \\ (1 + x)^{m} = \sum\limits_{i=0}\limits^{\infty}\binom{m}{i}x^{i} \\$$

两个形式幂级数相乘：

$$(1 + x)^{n}(1 + x)^{m} = (\sum\limits_{i=0}\limits^{\infty}\binom{n}{i}x^{i})(\sum\limits_{i=0}\limits^{\infty}\binom{m}{i}x^{i}) \\ \Rightarrow (1 + x)^{n+m} = \sum\limits_{i=0}\limits^{\infty}(\sum\limits_{k=0}\limits^{i}\binom{n}{k}\binom{m}{i-k})x^{i} \\$$

上式说明 $\{a_{i} = \sum\limits_{k=0}\limits^{i}\binom{n}{k}\binom{m}{i-k}\}$ 的母函数为 $(1 + x)^{m+n}$。

另一方面 $(1 + x)^{n+m}$ 是 $\{a_{i} = \binom{n+m}{i}\}$ 的母函数。因此：

$$\binom{m+n}{k} = \sum\limits_{i=0}\limits^{k}\binom{m}{i}\binom{n}{k-i}$$

---

朱世杰恒等式

朱世杰恒等式如下：

$$\binom{m+n+1}{n+1} = \sum\limits_{i=0}\limits^{m}\binom{n+i}{n}$$

朱世杰恒等式中令 n=k, m=n-k，得到以下恒等式：

$$\binom{n+1}{k+1} = \sum\limits_{i=0}\limits^{n-k}\binom{k+i}{k} = \sum\limits_{i=k}\limits^{n}\binom{i}{k}$$

比较系数法

比较等式：

$$(x+1)^{m+n+1} = \underbrace{(x+1)(x+1)\cdots(x+1)}_{m+n+1个}$$

比较两边 $x^{n+1}$ 的系数，左边 $x^{n+1}$ 的系数为 $\binom{m+n+1}{n+1}$；

右边 $x^{n+1}$ 的系数可以视为从 $m+n+1$ 项中选取 $n+1$ 项利用其中的 $x$ 的方法数。此时按照产生第一个 $x$ 的位置分类，第一个 $x$ 取自第 $j$ 项时，再剩余的 $m+n+1-j$项内选取其他 $n$ 个 $x$，则剩余的项数至少为 $n$，至多为 $n+m$，且有 $\binom{m+n+1-j}{n}$ 种选取方式得到 $x^{n}$，因此右端 $x^{n+1}$ 的系数为：

$$\sum\limits_{j=1}\limits^{m+1}\binom{m+n+1-j}{n} = \sum\limits_{i=0}\limits^{m}\binom{n+i}{n}$$

判断母函数相等

应用本文前面推导过的结论 $\{\binom{n+m}{n}\}_{m=0}^{\infty} \leftrightarrow \frac{1}{(1-x)^{n+1}}$。

构造母函数：$\{a_{m}\}_{m=0}^{\infty} \leftrightarrow f(x)$，$a_{m} = \binom{n+m-1}{n-1}$，可以推导出 $f(x) = \frac{1}{(1-x)^{n}}$。

$a_{m}$ 的前缀和数列 $\{b_{m}\}_{m=0}^{\infty}, b_{m} = \sum\limits_{k=0}\limits^{m}\binom{n+k-1}{n-1}$，其母函数为 $g(x)$。根据母函数的性质，有：

$$g(x) = \frac{1}{1 - x}\frac{1}{(1 - x)^{n}} = \frac{1}{(1 - x)^{n+1}}$$

另一方面 $\{\binom{n+m}{n}\}_{m=0}^{\infty} \leftrightarrow \frac{1}{(1-x)^{n+1}}$，因此：

$$\binom{m+n}{n} = \sum\limits_{k=0}\limits^{m}\binom{n-1+k}{n-1}$$

---

求递推关系的通项公式

斐波那契数列

$\{a_{n}\}$，$a_{n} = a_{n-1} + a_{n-2}$，$a_{0} = 1$, $a_{1}=1$，求 $a_{n}$。

要求 $\{a_{n}\}$，构造母函数 $f(x) = \sum\limits_{n=0}\limits^{\infty}a_{n}x^{n}$。

$$f(x) = 1 + x + \sum\limits_{n=2}\limits^{\infty}a_{n}x^{n} \\ -xf(x) = - x - \sum\limits_{n=2}\limits^{\infty}a_{n-1}x^{n} \\ -x^{2}f(x) = - \sum\limits_{n=2}\limits^{\infty}a_{n-2}x^{n} \\$$

上面三个式子相加，得到：

$$(1 - x - x^{2})f(x) = 1 + \sum\limits_{n=2}\limits^{\infty}(a_{n} - a_{n-1} - a_{n-2})x^{n}$$

因此 $f(x) = \frac{1}{1 - x - x^{2}}$ 为 $\{a_{n}\}$ 的母函数。

首先求 $1 - x - x^{2} = 0$ 的根 $r_{1} = \frac{-1+\sqrt{5}}{2}$, $r_{2} = \frac{-1-\sqrt{5}}{2}$，然后将 $f(x)$ 通过部分分式展开，得到：

$$f(x) = \frac{1}{r_{2}-r_{1}}(\frac{1}{x-r_{1}} - \frac{1}{x-r_{2}})$$

将形式幂级数代入：

$$f(x) = \sum\limits_{n=0}\limits^{\infty}(\frac{1}{r_{2}-r_{1}}(\frac{1}{r_{2}^{n+1}} - \frac{1}{r_{1}^{n+1}}))x^{n}$$

因此：

$$\begin{align} a_{n} &= \frac{1}{r_{2}-r_{1}}(\frac{1}{r_{2}^{n+1}} - \frac{1}{r_{1}^{n+1}}) \\ &= \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{n+1} - (\frac{1-\sqrt{5}}{2})^{n+1}) \end{align}$$

---

求微分方程

$x^{2}y’’ + xy’ + x^{2}y = 0$

设 $y = \sum\limits_{n=0}\limits^{\infty}a_{n}x^{n}$，于是 $y’ = \sum\limits_{n=1}\limits^{\infty}na_{n}x^{n-1}$，$y’’ = \sum\limits_{n=2}\limits^{\infty}n(n-1)a_{n}x^{n-2}$。

凑出微分方程中的各个项：

$$\left\{ \begin{array}{**lr**} x^{2}y = \sum\limits_{n=0}\limits^{\infty}a_{n}x^{n+2} = \sum\limits_{n=2}\limits^{\infty}a_{n-2}x^{n} \\ xy' = \sum\limits_{n=1}\limits^{\infty}na_{n}x^{n} \\ x^{2}y'' = \sum\limits_{n=2}\limits^{\infty}n(n-1)a_{n}x^{n} \\ \end{array} \right.$$

由 $x^{2}y’’ + xy’ + x^{2}y = 0$，得：

$$\begin{align} &\sum\limits_{n=2}\limits^{\infty}a_{n-2}x^{n} + \sum\limits_{n=1}\limits^{\infty}na_{n}x^{n} + \sum\limits_{n=2}\limits^{\infty}n(n-1)a_{n}x^{n} = 0 \\ \Rightarrow \quad &a_{1}x + \sum\limits_{n=2}\limits^{\infty}(n(n-1)a_{n} + na_{n} + a_{n-2})x^{n} = 0 \\ \Rightarrow \quad &a_{1}x + \sum\limits_{n=2}\limits^{\infty}(n^{2}a_{n}+a_{n-2})x^{n} = 0 \\ \end{align}$$

若要次等式成立，需要 $a_{1} = 0$，$n^{2}a_{n} + a_{n-2} = 0, n=2,3,\cdots$。也就是需要 $a_{n} = \frac{a_{n-2}}{n^{2}}$，因此 $a_{2n+1} = 0$。

找一个特解可以令 $a_{0} = 1$，可以推出 $a_{2n} = \frac{(-1)^{n}}{2^{2n}(n!)^{2}}$。因此：

$$y = \sum\limits_{n=0}\limits^{\infty}a_{2n}x^{2n} = \sum\limits_{n=0}\limits^{\infty}(-1)^{n}\frac{1}{(n!)^{2}}(\frac{x}{2})^{2n}$$

上面的函数正是零阶贝塞尔函数 $J_{0}(x) = \sum\limits_{n=0}\limits^{\infty}\frac{(-1)^{n}}{n!\Gamma(n+1)}(\frac{x}{2})^{2n}$。

---