最后更新: 2025-12-14 14:23 查看: 159 次纠错评论(0) 课件开VIP

生成函数的定义

## 生成函数的定义

**定义** （生成函数）已知序列 $\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）数列的通项公式方法之一，因此，我们也从斐波那契数列谈起

> **生成函数**（Generating Function）的核心思想是：**将一个数列编码成一个幂级数的系数**，从而利用级数的运算和性质来研究数列本身。
简单说，如果有一个数列 $ a_0, a_1, a_2, \dots $，我们可以把它“放进”一个函数里：$G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots = \sum_{n=0}^{\infty} a_n x^n$
这个$ G(x) $ 就是数列 $\{a_n\}$ 的**普通生成函数**

## 斐波那契数列
 斐波那契数，其定义为 $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$ 与我们所关心的概率项有关时，生成函数就会有一个很好的形式．

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

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：生成函数的引入

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

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