22._生成函数的定义

生成函数的定义

定义 （生成函数）已知序列 {an}n=0∞\left\{a_n\right\}_{n=0}^{\infty} ．它的生成函数被定义为

Ga(s)=∑n=0∞ansnG_a(s)=\sum_{n=0}^{\infty} a_n s^n

其中，ss 是使这个和收敛的任意数．

标准惯例是使用字母 ss 作为变量，然而它只是个虚拟变量，我们可以使用任何字母：s, xs, ~ x ， 或其它字母。

从更根本的的观点除非，生成函数犹如高中所学的，寻找数列的通项公式。

数学家拉普拉斯Laplace在其1812年出版的《概率的分析理论》中最先提出生成函数。而生成函数是推导斐波那契（Fibonacci）数列的通项公式方法之一，因此，我们也从斐波那契数列谈起

斐波那契数列

斐波那契数，其定义为 F0=0F_0=0 ， F1=1F_1=1 ，一般形式为

Fn=Fn−1+Fn−2\boxed{ F_n=F_{n-1}+F_{n-2} }

它的前几项是 0,1,1,2,3,5,8,13,⋯0,1,1,2,3,5,8,13, \cdots ．

斐波那契数来源背景：如果每对兔子（一雄一雌）每月能生殖一对小兔子（也是一雄一雌，下同），每对兔子第一个月没有生殖能力，但从第二个月以后便能每月生一对小兔子.假定这些兔子都没有死亡现象，那么从第一对刚出生的兔子开始，12 个月以后会有多少对兔子呢？ 解释说明为：一个月：只有一对兔子；第二个月：仍然只有一对兔子；第三个月：这对兔子生了一对小兔子， 共有 1+1=2 对兔子.第四个月：最初的一对兔子又生一对兔 子，共有 2+1=3 对兔子.则由第一个月到第十二个月兔子的 对数分别是,0，1，1，2，3，5，8，13，21，34，55，89，144， ……，后人为了纪念提出兔子繁殖问题的斐波纳契， 将这个兔子数列称为斐波那契数列， 即把,0，1，1，2，3，5，8，13，21，34……这样的数列称为斐波那契数列

从原则上说，斐波那契数不存在任何奥秘，因为它有明确的公式，我们可以求出序列中的任何项．在实际应用中，这个公式显然不适用于较大的 nn ．虽然我们可以求出 F10=55F_{10}=55 ，但是计算 F100=354224848179261915075F_{100}=354224848179261915075 会是件相当乏味无聊的事。如果用纸笔去计算 F2011F_{2011} ，则要引起警觉，因为它超过了 400位数字！

现在来展示生成函数是如何确定任意一个斐波那契数的，而不必计算之前的任何项！这个生成函数是

GF(s)=∑n=0∞FnsnG_F(s)=\sum_{n=0}^{\infty} F_n s^n

我们单独给出 n=0n=0 和 n=1n=1 时的项．当 n⩾2n \geqslant 2 时，利用定义中的递推关系 Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} 可得

GF(s)=F0+F1s+∑n=2∞(Fn−1+Fn−2)sn=0+s+∑n=2∞Fn−1sn+∑n=2∞Fn−2sn\begin{aligned} G_F(s) & =F_0+F_1 s+\sum_{n=2}^{\infty}\left(F_{n-1}+F_{n-2}\right) s^n \\ & =0+s+\sum_{n=2}^{\infty} F_{n-1} s^n+\sum_{n=2}^{\infty} F_{n-2} s^n \end{aligned}

注意，最后两个和式几乎就是原来的生成函数——不同之处在于 ss 的方幂不一样，并且这两个和式不是从 n=0n=0 开始计数的。这个问题可以通过提出 ss 的某些方幂，然后重新对和式进行标记来解决。这是论证中最困难的部分，但在考察过大量例子之后，它最终会成为一件自然而然的事情：

GF(s)=s+s∑n=2∞Fn−1sn−1+s2∑n=2∞Fn−2sn−2=s+s∑m=1∞Fmsm+s2∑m=0∞Fmsm\begin{aligned} G_F(s) & =s+s \sum_{n=2}^{\infty} F_{n-1} s^{n-1}+s^2 \sum_{n=2}^{\infty} F_{n-2} s^{n-2} \\ & =s+s \sum_{m=1}^{\infty} F_m s^m+s^2 \sum_{m=0}^{\infty} F_m s^m \end{aligned}

因为 F0=0F_0=0 ，所以第一个和式也可以扩展成从 m=0m=0 开始计数的形式．上面两个和式就是 GF(s)G_F(s) ，于是有

GF(s)=s+sGF(s)+s2GF(s)G_F(s)=s+s G_F(s)+s^2 G_F(s)

接下来，利用二次公式可得

GF(s)=s1−s−s2....(19.1)G_F(s)=\dfrac{s}{1-s-s^2} . ...(19.1)

非常好，我们已经确定了斐波那契数的生成函数：这对我们有什么帮助呢？ 虽然看起来似乎并非如此，但我们确实取得了相当大的进展．之所以取得如此大的进展，是因为式（19．1）的左端和右端都是关于 ss 的函数．在等式的左端，sns^n 的系数是 FnF_n ，因此，右端 sns^n 的系数也一定是 FnF_n ．也就是说，目前还不清楚右端 sns^n 的系数是什么．一个自然的想法是利用几何级数展开：

11−(s+s2)=∑k=0∞(s+s2)k=∑k=0∞∑l=0k(kl)sl(s2)k−l\frac{1}{1-\left(s+s^2\right)}=\sum_{k=0}^{\infty}\left(s+s^2\right)^k=\sum_{k=0}^{\infty} \sum_{l=0}^k\binom{k}{l} s^l\left(s^2\right)^{k-l}

从而有

s1−s−s2=∑k=0∞∑l=0k(kl)s2k−l+1\frac{s}{1-s-s^2}=\sum_{k=0}^{\infty} \sum_{l=0}^k\binom{k}{l} s^{2 k-l+1}

从这个等式中看出 ss 的方幂并不容易．（但这是个很好的练习，它引出了一个有趣的斐波那契数公式！）

幸运的是，有一种更好的方法来考察右端的式子．这又回到了微积分中最不受欢迎的一种积分方法：部分分式．不必惊讶，微积分里学过了有理函数的积分：除了用在这里之外，部分分式还会在解微分方程时出现．我们把 1−s−s21-s-s^2分解成 (1−As)(1−Bs)=1−(A+B)s+ABs2(1-A s)(1-B s)=1-(A+B) s+A B s^2 ，并写成

s1−s−s2=a1−As+b1−Bs,\frac{s}{1-s-s^2}=\frac{a}{1-A s}+\frac{b}{1-B s},

然后用几何级数展开每个分式．这样做的原因是，我们想利用几何级数公式，所以把它写成了 (1−As)(1−Bs)(1-A s)(1-B s) ，而不是 −(s−C)(s−D)-(s-C)(s-D) ．为了使用几何级数公式，我们希望分母看起来是 1 减去一个较小的数．注意，如果 ∣s∣<min⁡(1/∣A∣,1/∣B∣)|s|<\min (1 /|A|, 1 /|B|) ，那么 ∣As∣|A s| 和 ∣Bs∣|B s| 都会小于 1 ，这样就能利用几何级数公式了．

通过简单的代数运算（或者利用二次公式），我们可以得到 AA 和 BB 的值．现在有 A+B=1A+B=1 和 AB=−1A B=-1 ．于是，B=−1/AB=-1 / A 且 A−1/A=1A-1 / A=1 ，或者 A2−A−1=0A^2-A-1=0 ．因此，A=1±52A=\frac{1 \pm \sqrt{5}}{2} ．我们取正号，进行简单的计算就可以得到 B=1−52B=\frac{1-\sqrt{5}}{2}（如果取负号， AA 和 BB 的值就会颠倒过来）．

接下来计算 aa 和 bb ：

s1−s−s2=a1−As+b1−Bs=a+b−(aB+bA)s(1−As)(1−Bs)\frac{s}{1-s-s^2}=\frac{a}{1-A s}+\frac{b}{1-B s}=\frac{a+b-(a B+b A) s}{(1-A s)(1-B s)}

注意，上面是一个等式，它必须适用于 ss 的所有值．由于分母是相同的，唯一可能的情况就是两个分子相等。每个分子都是关于 ss 的多项式：这两个多项式对任意一个 ss 均相等的可能情况只有一种——它们肯定是同一个多项式，也就是说它们的系数一定相等。

看看常数项，我们发现 a+b=0a+b=0 ，所以 b=−ab=-a ．现在考察 ss 项的系数．我们需要让 −(aB+bA)=1-(a B+b A)=1 ．根据 AA 和 BB 的取值以及 b=−ab=-a 这一事实，我们有

−a1−52+a1+52=1-a \frac{1-\sqrt{5}}{2}+a \frac{1+\sqrt{5}}{2}=1

或者 a=1/5a=1 / \sqrt{5} ，进而有 b=−1/5b=-1 / \sqrt{5} ．现在已经证明了

GF(s)=s1−s−s2=1511−As−1511−Bs.G_F(s)=\frac{s}{1-s-s^2}=\frac{1}{\sqrt{5}} \frac{1}{1-A s}-\frac{1}{\sqrt{5}} \frac{1}{1-B s} .

现在利用几何级数展开，于是有

GF(s)=15∑n=0∞Ansn−15∑n=0∞Bnsn=∑n=0∞[15(1+52)n−15(1−52)n]sn.\begin{aligned} G_F(s) & =\frac{1}{\sqrt{5}} \sum_{n=0}^{\infty} A^n s^n-\frac{1}{\sqrt{5}} \sum_{n=0}^{\infty} B^n s^n \\ & =\sum_{n=0}^{\infty}\left[\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n\right] s^n . \end{aligned}

我们已经找到并证明了求第 nn 个斐波那契数的公式．

斐波那契公式(也叫比内公式)：设 {Fn}n=0∞\left\{F_n\right\}_{n=0}^{\infty} 表示斐波那契级数，其中 F0=0,F1=1F_0=0, F_1=1 ，并且 Fn+2=F_{n+2}= Fn+1+FnF_{n+1}+F_n ．于是

Fn=15(1+52)n−15(1−52)n\boxed{ 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 }

比内公式很惊人．现在我们可以直接找到序列中的任意一项，而不必计算之前所有项 对此，我一直很惊讶．斐波那契数是整数，而这个表达式包含了除法和平方根，但它最终却能给出整数．

经过这么长时间的论述，不妨回头看看我们都做了什么．我们从斐波那契数的关系式开始．虽然可以用这个关系式找到任意一项，但非常耗时．我们还把斐波那契数与一个生成函数 GF(s)G_F(s) 联系起来．神奇的是，GF(s)G_F(s) 有个很好的解析表达式，从中可以推导出斐波那契数的一个很好的公式．

值得强调的是，GF(s)G_F(s) 的形式非常好．如果随机取一个关于 ana_n 的数列，那么这种奇迹是不可能发生的．幸运的是，在很多问题中，当 ana_n 与我们所关心的概率项有关时，生成函数就会有一个很好的形式．

本节的其余部分可以放心地跳过．然而，由于奇迹很罕见，所以有必要了解为什么会发生这样的事情．我们试图回答为什么有必要构造一个生成函数．毕竟，如果它与原来的数据列相同，又能得到什么呢？对我们来说，关于斐波那契数列的结论只是种幸运，还是说这种情况会再次发生？生成函数最重要的优点是有助于简化概率中的代数运算．我们不断强调，在实践中，尽量简化代数运算会非常有用．除了会经常出错外，表达式越复杂，我们就越不容易看出其中的规律和关联．简化代数运算可以启发我们找到事物之间的联系，还能大大减少计算量．

Previous21._生成函数的引入
Next23._生成函数的唯一性和收敛性