生成函数与数列

由通项公式求生成函数

博客的表格生成有点问题，直接放个图。

其中 (3)(6) 可用 $\frac{1}{1-x}$ 泰特展开证明，(5)可用广义二项式定理证明，这里不过多介绍。

由生成函数求通项公式

已知数列 $\{a_n\}$ 的递推公式，用生成函数求通项公式的步骤如下

1. 把 $a_n$ 用其他项表示成唯一一个方程，该方程对任意 $n \in \mathbb{N}$ 都成立，并定义 $a_{-n}=0~(n > 0)$
2. 乘上 $x^n$ ，并对方程两边求和，左边就是 $\sum_{n \geq 0} a_n x^n=A(x)$ ，右边整理成关于 $A(x)$ 和 $x$ 的式子
3. 解出 $A(x)$ ，此时应是封闭形式
4. 展开为幂级数形式，则第 $n$ 项的系数即为答案。

对于第四步，一般可以套用上面的表格，否则

• 如果出现分式，考虑分解成 $\frac{a}{1 - \rho x}$ 的形式
• 如果有 $\ln,\exp$ 等函数，考虑泰勒展开。
• 如果出现根式，考虑广义二项式定理。
• 如果出现单独的 $x$ 变量，考虑拉格朗日反演。

---

例1：推导斐波那契数列的通项，这里定义 $f_0=0,~f_1=1,~f_n = f_{n-1} + f_{n-2}\,(n \ge 2)$

解：（这都什么经典老题了）由于只能有一个方程，因此我们将初值整合进递推式内

$$f_n = f_{n-1} + f_{n-2} + [n=1]$$

乘上 $x^n$ 并求和

$$\sum_{n \geq 0} f_n x^n=\sum_{n \geq 0} f_{n-1} x^n+\sum_{n \geq 0} f_{n-2} x^n+x^1$$

根据生成函数中系数平移的定义

$$F(x) = xF(x) + x^2F(x) + x$$

解得

$$F(x) = \frac{x}{1-x-x^2}$$

于是我们就得到了 $F(x)$ 的封闭形式，考虑对其展开成级数形式。

这里有个套路，对于形如 $\frac{f(x)}{(1-ax)(1-bx)^{m}}$ 的封闭形式，考虑将原式拆成若干项形如 $\frac{1}{1-\rho x}$ 的式子之和，即

$$\frac{A}{1-ax} + \frac{B_1}{(1-bx)^{m}}+\frac{B_2}{(1-bx)^{m-1}}+\cdots + \frac{B_m}{(1-bx)}$$

在本题里显然 $m=1$ ，属于比较简单的情况。

不妨设 $\left(1-\rho_1 x\right)\left(1-\rho_2 x\right)=1-x-x^2$ ，得到

$$\begin{cases} \rho_1 \rho_2=-1 \\[8pt]\rho_1+\rho_2=-1 \end{cases}$$

可知 $\rho_1,\rho_2$ 为方程 $x^2-x-1 = 0$ 的根，解得 $\rho_1 = \frac{1-\sqrt{5}}{2},~\rho_2 = \frac{1 + \sqrt{5}}{2}$ 。

代回原式，并把分子乘上系数凑成 $x$ ，得到

$$F(x)=\frac{1}{\sqrt{5}}\left(-\frac{1}{1-\frac{1-\sqrt{5}}{2} x}+\frac{1}{1-\frac{1+\sqrt{5}}{2} x}\right)$$

到这里用表格就可以得到最终答案了

$$f_n=-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n+\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n$$

实际上，出现的方程 $x^2-x-1=0$ 就是特征根法求数列通项中的特征根方程

而分母将系数凑成 $x$ 的过程就相当于特征根法中将初始值代入解出系数。

---

例2：求卡特兰数的通项公式。卡特兰数 $c_n$ 定义为 $n$ 个点无标号无根树的数量

首先递推式 $c_n = [n=0] + \sum_{i=0}^{n-1}c_ic_{n-i-1}$ ，设它的 OGF 为 $C(x)$ ，两边乘上 $x^n$ 并求和

$$\begin{aligned} & \sum_{n \geq 0} c_n x^n=1+\sum_{n \geq 1} \sum_{i=0}^{n-1} c_i c_{n-i-1} x^n \\ & C(x)=1+x \sum_{n \geq 1} \sum_{i=0}^{n-1} c_i c_{n-i-1} x^{n-1} \end{aligned}$$

仔细观察可以发现，后面那一堆就是 $C(x)\cdot C(x)$ 的第 $n-1$ 项系数，于是

$$C(x) = 1 + xC^2(x)$$

通过求根公式解得

$$C(x) = \frac{1 \pm\sqrt{1 - 4x}}{2x}$$

因为一个数列 $f$ 的生成函数 $F(x)$ 一定满足 $F(0)=f_0$ 或 $\lim_{x\to 0}F(x) = f_0$ 。

所以容易发现，当 $x \to 0$ 时，仅有

$$\lim _{x \rightarrow 0} \frac{1-\sqrt{1-4 x}}{2 x}=\lim _{x \rightarrow 0} \frac{-\frac{1}{2 \sqrt{1-4 x}} \cdot(-4)}{2}=1=f_0$$

接着我们要展开 $\frac{1-\sqrt{1-4 x}}{2 x}$ 。根据广义二项式定理有

$$\sqrt{1-4 x}=\sum_n\left(\begin{array}{c} \frac{1}{2} \\ n \end{array}\right)(-4 x)^n$$

其中

$$\left(\begin{array}{c} \frac{1}{2} \\ n \end{array}\right)=\frac{\frac{1}{2}\left(\frac{1}{2}-1\right) \cdots\left(\frac{1}{2}-n+1\right)}{n !}=\frac{(-1)^{n-1} 1 \times 1 \times 3 \times \cdots \times(2 n-3)}{2^n n !}=\frac{(-1)^{n-1}(2 n-2) !}{2^{2 n-1} n !(n-1) !}$$

因此

$$\sqrt{1-4 x}=-2 \sum_n \frac{(2 n-2) !}{n !(n-1) !} x^n$$

进而

$$\frac{1-\sqrt{1-4 x}}{2 x}=\sum_{n \geq 0} \frac{(2 n) !}{n !(n+1) !} x^n=\sum_{n \geq 0} \frac{\left(\begin{array}{c} 2 n \\ n \end{array}\right)}{n+1} x^n$$

即 $c_n = \frac{\binom{2n}{n}}{n+1}$ 。当然，还有一种更为简单的推导，需要用到拉格朗日反演。

---

参考文献：

[1] https://www.cnblogs.com/birchtree/p/11575252.html