生成函数

生成函数是一种用于解决与序列有关的问题的强力工具。通过生成函数，我们可以将一个序列映射为一个函数，并将对序列的操作映射为对这个函数的操作，从而轻松解出在序列视角下难以解决的问题。

类似傅里叶变换和拉普拉斯变换，生成函数的本质是 从另一个方式看待序列 ，或是 在另一个“同构”的空间中处理序列问题 。

生成函数的定义

对于一个序列 ${a_{i}}$ ，它的 普通生成函数 （OGF）定义如下:

$f (s) = \sum_{i = 0}^{\infty} a_{i} s^{i}$

其中， $s$ 是一个形式变量，可以表示任何使这个求和收敛的数。
例如，对于数列 $a_{n} = n$ ，它的生成函数就是 $f (s) = s^{1} + 2 s^{2} + 3 s^{3} . . .$
在本文中我们使用 $O G F (a_{n})$ 来表示数列 $a_{n}$ 的生成函数。

生成函数的性质

前面说到过，我们可以将对序列的操作变为对生成函数的操作。生成函数与原序列有以下性质：

序列之和的生成函数是生成函数之和 ：对于序列 $a_{n}, b_{n}$ ，有 $O G F (a_{n} + b_{n}) = O G F (a_{n}) + O G F (b_{n})$ 。
序列乘标量的生成函数是生成函数乘标量：对于序列 $a_{n}$ ，有 $O G F (k a_{n}) = k O G F (a_{n})$ 。
序列的卷积的生成函数是生成函数之积 ：对于序列 $a_{n}, b_{n}$ ，有 $O G F (a_{n} \times b_{n}) = O G F (a_{n}) O G F (b_{n})$ 。
前缀和性质 ：对于序列 $a_{n}$ ，若 $b_{n} = \sum_{i = 0}^{n} a_{i}$ ，则 $O G F (b_{n}) = \frac{O G F (a_{n})}{1 - s}$ ，其中 $s$ 是生成函数中的形式变量。
差分性质：对于序列 $a_{n}$ ，若 $b_{n} = a_{n} - a_{n - 1}, b_{0} = a_{0}$ ，则 $O G F (b_{n}) = (1 - s) O G F (a_{n})$ ，其中 $s$ 是生成函数中的形式变量。

生成函数的封闭形式

生成函数的真正强大之处在于，它可以借助序列自身的特性写成一个简单的封闭形式。考虑斐波那契数列 $f i b_{n}$ ，它的生成函数为 $f (s) = \sum_{i = 1}^{\infty} f i b_{i} s^{i}$ 。我们将前面两项单列出来：

$f (s) = s + \sum_{i = 2} f i b_{i} s^{i}$

因为 $f i b_{n} = f i b_{n - 1} + f i b_{n - 2}$ ，代入可知：

$\begin{aligned} f (s) & = s + \sum_{i = 2}^{\infty} (f i b_{i - 1} + f i b_{i - 2}) s^{i} \\ = s + \sum_{i = 2}^{\infty} f i b_{i - 1} s^{i} + \sum_{i = 2}^{\infty} f i b_{i - 2} s^{i} \end{aligned}$

我们将 $s$ 从后面两项中提取出来，使得 $f i b$ 的下标与 $s$ 的幂次统一：

$\begin{aligned} f (s) & = s + s \sum_{i = 2}^{\infty} f i b_{i - 1} s^{i - 1} + s^{2} \sum_{i = 2}^{\infty} f i b_{i - 2} s^{i - 2} \\ = s + s (f (s)) + s^{2} (f (s)) \\ = s + s f (s) + s^{2} f (s) \end{aligned}$

这是一个一次方程，可以解得 $f (s) = \frac{s}{1 - s - s^{2}}$ 。

由封闭解解出通项

现在的问题是，如何由这个数列得到斐波那契数列的通项？我们首先介绍一下 几何级数 。

几何级数是这样的级数： $s = 1 + x + x^{2} + . . .$ 。当 $- 1 < x < 1$ 时，因为 $s = s * x + 1$ ，因此 $s = \frac{1}{1 - x}$ 我们可以利用这一点，把 $f (s)$ 进行展开：

$\begin{aligned} f (s) & = s * \frac{1}{1 - (s + s^{2})} \\ = s * \sum_{i = 0}^{\infty} (s + s^{2})^{i} \\ = s * \sum_{i = 0}^{\infty} \sum_{j = 0}^{i} (\binom{i}{j}) s^{j} s^{2 (i - j)} \\ = \sum_{i = 0}^{\infty} \sum_{j = 0}^{i} (\binom{i}{j}) s^{2 i - j + 1} \end{aligned}$

通过把这个级数进一步展开，我们就可以得到斐波那契数列的通项公式。但实际上由于用到了二项式定理，这个展开会非常麻烦，因此我们可以在使用几何级数进行展开之前，先使用 部分分式 将原式拆成两个简单的分式：

$\begin{aligned} 设 \frac{s}{1 - s - s^{2}} = \frac{A}{1 - a s} + \frac{B}{1 - b s} \\ 解得 {\begin{cases} a = \frac{1 + \sqrt{5}}{2} \\ b = \frac{1 - \sqrt{5}}{2} \\ A = \frac{1}{\sqrt{5}} \\ B = - \frac{1}{\sqrt{5}} \end{cases} \\ 那么 \frac{s}{1 - s - s^{2}} = \frac{1}{\sqrt{5}} \frac{1}{1 - a s} - \frac{1}{\sqrt{5}} \frac{B}{1 - b s} \\ = \frac{1}{\sqrt{5}} \sum_{i = 0}^{\infty} (a s)^{i} - (b s)^{i} \\ = \frac{1}{\sqrt{5}} \sum_{i = 0}^{\infty} (a^{i} - b^{i}) s^{i} \\ = \sum_{i = 0}^{\infty} \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{i} - (\frac{1 - \sqrt{5}}{2})^{i}) s^{i} \end{aligned}$

因此， $f i b_{n} = \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{n} - (\frac{1 - \sqrt{5}}{2})^{n})$ 。这个公式被称为 比内公式

除了使用几何级数以外，我们还可以使用 泰勒展开 来进行还原：泰勒公式将函数写成多项式的形式，而这天然就和我们想要的形式一致。考虑 $f (s) = e^{x}$ ，进行泰勒展开可知 $f (s) = \sum_{i = 0}^{\infty} \frac{x^{i}}{i!}$ 可知， $e^{x}$ 是数列 $a_{n} = \frac{1}{n!}$ 的生成函数。