生成函数与数列
由通项公式求生成函数
博客的表格生成有点问题，直接放个图。
其中 (3)(6) 可用 \(\frac{1}{1-x}\) 泰特展开证明，(5)可用广义二项式定理证明，这里不过多介绍。
由生成函数求通项公式
已知数列 \(\{a_n\}\) 的递推公式，用生成函数求通项公式的步骤如下
- 把 \(a_n\) 用其他项表示成唯一一个方程，该方程对任意 \(n \in \mathbb{N}\) 都成立，并定义 \(a_{-n}=0~(n > 0)\)
- 乘上 \(x^n\) ，并对方程两边求和，左边就是 \(\sum_{n \geq 0} a_n x^n=A(x)\) ，右边整理成关于 \(A(x)\) 和 \(x\) 的式子
- 解出 \(A(x)\) ，此时应是封闭形式
- 展开为幂级数形式，则第 \(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}\) 。当然，还有一种更为简单的推导，需要用到拉格朗日反演。
参考文献：
