最后更新: 2025-05-02 08:02 查看: 45 次反馈刷题

生成函数的定义

## 生成函数的定义

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

$$
G_a(s)=\sum_{n=0}^{\infty} a_n s^n
$$

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

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

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

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

## 斐波那契数列
 斐波那契数，其定义为 $F_0=0$ ， $F_1=1$ ，一般形式为 
 
 $$
 \boxed{
 F_n=F_{n-1}+F_{n-2}
 }
 $$ 
 
 它的前几项是 $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……这样的数列称为斐波那契数列
 
 
 
从原则上说，斐波那契数不存在任何奥秘，因为它有明确的公式，我们可以求出序列中的任何项．在实际应用中，这个公式显然不适用于较大的 $n$ ．虽然我们可以求出 $F_{10}=55$ ，但是计算 $F_{100}=354224848179261915075$ 会是件相当乏味无聊的事。如果用纸笔去计算 $F_{2011}$ ，则要引起警觉，因为它超过了 400位数字！

现在来展示生成函数是如何确定任意一个斐波那契数的，而不必计算之前的任何项！这个生成函数是
$$
G_F(s)=\sum_{n=0}^{\infty} F_n s^n
$$

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

$$
\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}
$$

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

$$
\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}
$$

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

$$
G_F(s)=s+s G_F(s)+s^2 G_F(s)
$$

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

$$
G_F(s)=\dfrac{s}{1-s-s^2} .  ...(19.1)
$$

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

$$
\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}
$$

从而有

$$
\frac{s}{1-s-s^2}=\sum_{k=0}^{\infty} \sum_{l=0}^k\binom{k}{l} s^{2 k-l+1}
$$
从这个等式中看出 $s$ 的方幂并不容易．（但这是个很好的练习，它引出了一个有趣的斐波那契数公式！）

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

$$
\frac{s}{1-s-s^2}=\frac{a}{1-A s}+\frac{b}{1-B s},
$$

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

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

接下来计算 $a$ 和 $b$ ：

$$
\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)}
$$

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

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

$$
-a \frac{1-\sqrt{5}}{2}+a \frac{1+\sqrt{5}}{2}=1
$$

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

$$
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} .
$$

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

$$
\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}
$$

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

**斐波那契公式(也叫比内公式)**：设 $\left\{F_n\right\}_{n=0}^{\infty}$ 表示斐波那契级数，其中 $F_0=0, F_1=1$ ，并且 $F_{n+2}=$ $F_{n+1}+F_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
}
$$

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

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

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

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

开VIP会员

非会员每天6篇，会员每天16篇，VIP会员无限制访问

题库训练自我测评投稿

上一篇：生成函数的引入

下一篇：生成函数的唯一性和收敛性

本文对您是否有用？有用 (0) 无用 (0)