您当前的位置：首页 > 当代文学 > 数学女孩1

4.2.1　斐波那契数列

4.2　抓住斐波那契数列的要害

我们转移到附近的咖啡店，草草点完单后又继续开始刚才的数列的话题。抓住数列的要害究竟是怎么回事呢？两个王国又到底是什么呢？听了我的问题，米尔嘉推了推眼镜说：“嗯，是啊。”

4.2.1　斐波那契数列

是啊。这个比喻可能不太符合逻辑，太夸张了。“在两个王国里穿梭漫步，抓住数列的要害”其实就是“运用生成函数来求数列的通项”呀。

现在给你看看“旅行地图”吧。首先，求得与数列相对应的生成函数。其次，将生成函数变形，求出生成函数的有限项代数式。然后再将有限项式根据幂级数展开，最终求得数列的通项。也就是说，通过生成函数来找出数列的通项。

“运用生成函数来求数列的通项”的“旅行地图”

例如，以数列中的斐波那契数列为例。你知道斐波那契数列吧？

$\langle0,1,1,2,3,5,8,\cdots\rangle$

这个数列从第三项开始，每一项都等于前两项之和。

$0,1,0+1=1,1+1=2,1+2=3,2+3=5,3+5=8,\cdots$

这个数列也有从 1 开始的情况，但是这里我们从 0 开始。

我们假设 Fn 为斐波那契数列的通项。F0 和 0 相等，F1 和 1 相等，当 n ≥ 2 时，则 $F_n=F_{n-2}+F_{n-1}$ ，所以 Fn 就被定义为表示各项间关系的推导公式。

斐波那契数列的定义（推导公式）

$F_n=\left{\begin{aligned}0\qquad\qquad\qquad&(n=0)\\1\qquad\qquad\qquad&(n=1)\\F_{n-2}+F_{n-1}\quad&(n\geq2)\end{aligned}$

“从第三项开始，每一项都等于前两项之和”——斐波那契数列的这个性质在这个定义中得到了充分的体现。另外，还可以像 F0, F1, F2, ... 这样计算出斐波那契数列。但是，Fn 没有表现为“关于 n 的有限项代数式”。也就是说，通项公式 Fn 中并未使用 n，不是关于 n 的直接代数式。这也就是我所说的“没有抓住数列的要害”状态。

现在我们假设要求斐波那契数列的第 1000 项是多少。一般情况下，我们就用 F0 + F1 来求 F2，用 F1 + F2 来求 F3，…… 如此重复计算后，最后通过求 F998 + F999 的和才能算出 F1000 的值。如果靠推导公式来计算 Fn 的话，那么要进行 n - 1 次加法计算。这实在太无聊了。我想将 Fn 表示成“关于 n 的有限项代数式”。“关于 n 的有限项代数式”究竟是什么意思呢？粗略地说，它就是“将大家都知道的运算方法在有限的次数内进行组合后得到的代数式”。

我很想将 Fn 表示成“关于 n 的有限项代数式”，抓住斐波那契数列的要害。

问题 4-1

将斐波那契数列的通项 Fn 表示成“关于 n 的有限项代数式”。

4.2.2　斐波那契数列的生成函数

那么，接下来我们就将与斐波那契数列相对应的生成函数称为 F(x)。也就是说，我们将其对应关系表现为以下形式。

在函数 F(x) 中，如果将 xn 这一项的系数用 Fn 来表示，那么整个函数就可以用以下式子表示出来。这样，我们就可以向生成函数的王国过渡了。

$\begin{aligned}F(x)&=F_0x^0+F_1x^1+F_2x^2+F_3x^3+F_4x^4+\cdots\\&=\enskip0x^0+\enskip1x^1+~~1x^2+\enskip2x^3+\enskip3x^4+\cdots\\&=\qquad\qquad~ x~+\enskip~~ x^2+\enskip2x^3+\enskip3x^4+\cdots\end{aligned}$

接下来，我想调查一下函数 F(x) 的性质。函数 F(x) 的系数 Fn 是斐波那契数列的通项，如果好好利用这点的话，我们很快就能找到关于函数 F(x) 的有趣性质。

斐波那契数列的性质究竟是什么呢？当然我们刚才已经求得推导公式 $F_n=F_{n-2}+F_{n-1}$ ，如果我们好好利用这个表示各项间关系的推导公式的话， $F_{n-2},F_{n-1},F_n$ 这样的系数就可以在 F(x) 的计算过程中出现。如下所示。

$F(x)=\cdots+\underline{F_{n-2}x^{n-2}}+\underline{F_{n-1}x^{n-1}}+\underline{F_nx^n}+\cdots$

我想把系数 $F_{n-2}$ 和 $F_{n-1}$ 相加试试看，但是 x 的幂次方互不相同，所以不能合并同类项。那该怎么办呢？

◎　　◎　　◎

米尔嘉看看我。嗯。x 的幂次方确实不同，不能将它们的系数直接相加。因为它们不是同类项，所以不能合并。将数列和生成函数相互对应，真的会发生有趣的现象吗？——终于，从米尔嘉嘴里吐出了一句：“很简单哦。”

4.2.3　封闭表达式

很简单哦。

x 的幂次方如果互不相同的话，将不同的部分乘上 x 就好了。同底数幂相乘，底数不变指数相加，也就是所谓的指数运算法则。

$x^{n-2}\cdot x^2=x^{n-2+2}=x^n$

例如， $F_{n-2}x^{n-2}$ 乘以 x2 的话得 $F_{n-2}x^n$ 。如下所示，如果巧妙地进行乘法运算的话，就可以统一为 xn 的形式。为了使形式统一，我们将 1 写作 x0。

$\left{\begin{aligned}F_{n-2}x^{n-2}\cdot x^2\quad&=\quad F_{n-2}x^n\\F_{n-1}x^{n-1}\cdot x^1\quad&=\quad F_{n-1}x^n\\F_{n-0}x^{n-0}\cdot x^0\quad&=\quad F_{n-0}x^n\end{aligned}$

这样一来，我们就可以运用与函数 F(x) 相对应的斐波那契数列的推导公式了。好，我们将 F(x) 分别和 x2, x1, x0 相乘后的式子写下来看看。

{%}

这样就统一了幂次项。利用式子 A、式子 B、式子 C，我们接着进行计算。这样一来，我们就可以运用同类项系数 Fn 的推导公式。

式子A +式子B -式子C

在进行计算的时候，式子左边就变成了以下形式。

然后，式子右边变为以下形式。

式子右边经计算就只剩下起始部分 F_0x^1-F_0x^0-F_1x^1 ，其他部分全都抵消了。为什么这么说呢？这是因为根据斐波那契数列的推导公式， $F_{n-2}+F_{n-1}-F_n$ 这部分等于 0，任何数乘以 0 都会马上消失。

我们已经没什么必要写成 x0 和 x1 的形式了，直接写 1 和 x 就可以了。那么，F0 就可以写成 0，F1 就可以写成 1。于是，我们得到了以下式子。

$F(x)\cdot(x^2+x-1)=-x$

两边同时除以 x^2+x-1 ，整理后就能求得 F(x) 的有限项代数式。这就是 F(x) 的庐山真面目哦。

$F(x)=\frac{x}{1-x-x^2}$

我看到斐波那契数列的生成函数变形成了这样一个简单的有限项代数式，心中雀跃无比。因为这个代数式包括了无限延续下去的斐波那契数列的全部内容，是一个高度浓缩的式子。

$\langle0,1,1,2,3,5,8\rangle\quad\longleftrightarrow\quad\frac{x}{1-x-x^2}$

斐波那契数列的生成函数 F(x) 的封闭表达式

$F(x)=\frac{x}{1-x-x^2}$

4.2.4　用无穷级数来表示

我们思考讨论了斐波那契数列的生成函数 F(x)。如果用 x 来表示 F(x) 的有限项代数式，x 的 n 次方前的系数应该是 Fn。

所以，接下来我们的目标是想办法将 $\frac{x}{1-x-x^2}$ 用 x 的无穷级数来表示。

我们曾经用下面的分式形式来表现过关于 x 的无穷级数。

$\frac{1}{1-x}=1+x+x^2+x^3+\cdots$

比如说，我们能否想办法将 $\frac{x}{1-x-x^2}$ 变成与 $\frac{1}{1-x}$ 类似的形式呢？如果可能的话，我们就能从生成函数的王国回到数列的王国了。回去的时候当然不能空手，请带一件生成函数王国的“土特产”噢。那就是斐波那契数列的通项公式。你觉得如何？

◎　　◎　　◎

米尔嘉盯着我的眼睛。啊，对了，接下来只要把生成函数 F(x) 写成无穷级数的形式，就可以求得斐波那契数列的通项公式了吧。我一直盯着生成函数的形式看，彻底弄清了其结构。

$F(x)=\frac{x}{1-x-x^2}$

分母 1-x-x^2 是个二次代数式。首先，先试试将 1-x-x^2 因式分解。我在练习本上又开始计算起来。米尔嘉一直在旁边盯着看。

假设有未知常数 r 和 s，式子 1-x-x^2 便可分解成以下形式。

1-x-x^2=(1-rx)(1-sx)

如果照上述式子那样分解的话，通过求下面式子的分数和，在通分的时候分母就正好可以变形成 1-x-x^2 的形式了。

计算这个式子，当它变形成 $\frac{x}{1-x-x^2}$ 的形式后，再求出 r 和 s 就可以了。

$\begin{aligned}\frac{1}{1-rx}+\frac{1}{1-sx}&=\frac{1-sx}{(1-rx)(1-sx)}+\frac{1-rx}{(1-rx)(1-sx)}\\&=\frac{2-(r+s)x}{1-(r+s)x+rsx^2}\\&=\cdots\end{aligned}$

嗯，只要我们顺利计算出 r 和 s 的值，分母 1-(r+s)x+rsx^2 就有可能变成 1-x-x^2 的形式。但是，分子 2-(r+s)x 却很难变形为 x 的形式，因为常数 2 无法被抵消。

当我在嘀咕时，米尔嘉在一旁提示说：“如果用这种方法，就能顺利进行下去哦。”

4.2.5　解决

如果用这种方法，就能顺利进行下去哦。

我们在分子里放入参数。也就是说，假设有 4 个未知常数 R，S，r，s，接着思考以下式子就好了。

$\frac{R}{1-rx}+\frac{S}{1-sx}$

计算此式。

$\begin{aligned}\frac{R}{1-rx}+\frac{S}{1-sx}&=\frac{R(1-sx)}{(1-rx)(1-sx)}+\frac{S(1-rx)}{(1-rx)(1-sx)}\\&=\frac{(R+S)-(rS+sR)x}{1-(r+s)x+rsx^2}\end{aligned}$

如果要使以下式子成立，只要确定常数 R，S，r，s 分别为多少就可以了。

$\frac{(R+S)-(rS+sR)x}{1-(r+s)x+rsx^2}=\frac{x}{1-x-x^2}$

比较等式左右两边后，只要解出以下联立方程组就可以了。

$\left{\begin{aligned}R+S\enskip&=\enskip~0\\rS+sR&=-1\\r+s\enskip&=\enskip~1\\rs\enskip\enskip&=-1\end{aligned}$

4 个未知数配有 4 个独立的等式。我们试着解一下这个联立方程组。

首先，将 R 和 S 分别转化成只含有 r 和 s 的关系式。

$R=\frac{1}{r-s},\qquad S=\frac{-1}{r-s}$

这样一来，就找到了用无穷级数来表示 F(x) 的头绪。我们先暂且不求出 r 和 s 具体为多少，继续推导下去。

$\begin{aligned}F(x)&=\frac{x}{1-x-x^2}\\&=\frac{x}{(1-rx)(1-sx)}\\&=\frac{R}{1-rx}+\frac{S}{1-sx}\end{aligned}$

这里将 $R=\frac{1}{r-s}$ ， $S=\frac{-1}{r-s}$ 代入。

$\begin{aligned}&=\frac{1}{r-s}\cdot\frac{1}{1-rx}-\frac{1}{r-s}\cdot\frac{1}{1-sx}\\&=\frac{1}{r-s}\biggl(\frac{1}{1-rx}-\frac{1}{1-sx}\biggr)\end{aligned}$

再将 $\frac{1}{1-rx}$ 用 $1+rx+r^2x^2+r^3x^3+\cdots$ 代入，将 $\frac{1}{1-sx}$ 用 $1+sx+s^2x^2+s^3x^3+\cdots$ 代入。

$\begin{aligned}&=\frac{1}{r-s}\Bigl(\Bigl(1+rx+r^2x^2+r^3x^3+\cdots\Bigr)-\Bigl(1+sx+s^2x^2+s^3x^3+\cdots\Bigr)\Bigr)\\&=\frac{1}{r-s}\Bigl((r-s)x+(r^2-s^2)x^2+(r^3-s^3)x^3+\cdots\Bigr)\\&=\frac{r-s}{r-s}x+\frac{r^2-s^2}{r-s}x^2+\frac{r^3-s^3}{r-s}x^3+\cdots\end{aligned}$