第4章斐波那契数列与生成函数

就我们所知，操作无穷级数来生成数列，

是使用数列最有力的方法。

——葛理翰／柯努斯／巴塔希尼克(陈衍文谭／儒林出版社)『具体数学』[21]

4．1图书室

现在是高二的秋天，我在放学后图书室教学妹——蒂蒂数学，目前正在展开一项简单的算式。

(a＋b)(a－b)＝(a＋b)a－(a＋b)b

＝aa＋ba－ab－bb

＝a<平方>－b<平方>

我将(a＋b)(a－b)展开成a<平方>－b<平方>后，向她说明可以把『两数和与差的积等于两数平方的差』这公式记下来，而她则是回答「我懂了，听了学长的教学，感觉原本零碎的知识都整合起来了」这句话。

米尔迦此时正好走进图书室，并直接走近我们，接着她突然踢开蒂蒂的椅子，巨大的声响让图书室里的人都往我们看过来，蒂蒂慌忙站起身，并被米尔迦瞪着直到她离开图书室，而我就这样呆站着目送蒂蒂出去。

米尔迦像没事一样扶好椅子坐下，目光瞄向笔记本，然后拉了拉我的袖子要我坐下，等到我坐下后，米尔迦问：

「推演算式？」

我回答因为学妹有问题所以教她……

米尔迦哼了一声，还将我手里的自动铅笔拿走，在笔记本上不停写着，然后说：「来寻找规律吧。」

4．1．1寻找规律

「来寻找规律吧。」最先是(1＋x)(1－x)的展开，这是(a＋b)(a－b)的特殊状况。

(1＋x)(1－x)＝(1＋x)×1－{1＋x)×x

＝(1＋x)－(x＋x<平方>)

＝1＋(x－x)－x<平方>

＝1－x<平方>

接下来将算式(1＋x)(1－x)中的(1＋x)以(1＋x＋x<平方>)代入。

(1＋x＋x<平方>)(1－x)＝(1＋x＋x<平方>)×1－(1＋x＋x<平方>)×x

＝(1＋x＋x<平方>)－(x＋x<平方>＋x<立方>)

＝1＋(x－x)＋(x<平方>－x<平方>)－x<立方>

＝1－x<立方>

规律很明显，中间项都消去了，只剩下三次项和常数项，用笔算的话会更容易理解，例如(1＋x＋x2＋x3)(1－x)会变成下列所示，明显地只剩下两项。

1＋x＋x<平方>＋x<立方>

×1－x——

－x－x<平方>－x<立方>－x<4次方>

1＋x＋x<平方>＋x<立方>——

1－x<4次方>

将其广义化，令n为0以上的数，之后则如下所示。

(1)(1－x)＝1－x1

(1＋x)(1－x)＝1－x<平方>

(1＋x＋x<平方>)(1－x)＝1－x<立方>

(1＋x＋x<平方>＋x<立方>)(1－x)＝1－x<4次方>

.

.

.

(1＋x＋x<平方>＋x<立方>＋x<4次方>＋……＋x<n次方>)(1－x)＝1－x<n次方>＋1

◎◎◎

……原来如此，不过这并没有想象中有趣，是很常见的展开与广义化，比起这个，我更在意刚刚被踢椅子的蒂蒂现在的状况，米尔迦却说出『到这里为止都很普通』后，就继续写下去。

4．1．2等比数列的和

「到这里为止都很普通。」那么接下来会怎么进行呢？将刚才的算式再写一次。

(1＋x＋x<平方>＋x<立方>＋x<4次方>＋……＋x<n次方>)(1－x)＝1－x<n次方>＋1

在这里将两边同除1－x，由于0不能当除数，所以假设1－x≠0。

1＋x＋x<平方>＋x<立方>＋x<4次方>＋……＋x<n次方>＝

到刚才为止都是关于『求积的公式』，而现在则是『求和的公式』:实际上，这就是等比数列的求和公式，说得更清楚一点，是第0项为1，公比为x的等比数列，也就是1，x，x<平方>，x<立方>，……，x<n次方>，……这个数列从第0项到第n项的和。

「那么，接下来要怎么发展呢？」

◎◎◎

……我则是回答『会自然想到等比数列的无穷级数吧』，不是到第n项为止的有限和，而是无限的和。「是啊。」米尔迦微笑着回答我。

4．1．3迈向无穷级数

「是啊，思考无穷级数吧。」

无穷级数1＋x＋x<平方>＋x<立方>＋……，被定义为这个等比数列部分和的极限。

1＋x＋x<平方>＋x<立方>＋x<4次方>＋……＋x<n次方>＝(1－x<n+1次方>)/(1－x)

当x的绝对值小于1，也就是|x|＜1时，使n→∞的话，会让x<n次方>＋1→0，也就是下式成立。

1＋x＋x<平方>＋x<立方>＋……＝1/(1－x)

这样就得到了无穷级数的公式，|x|＜1是为了在n→∞时，让x<n次方>＋1→0必要条件。

※※等比数列的无穷级数(等比级数的公式)

1＋x＋x<平方>＋x<立方>＋……＝1/(1－x)

这是第0项为1，公比为x的等比级数，且|x|＜1。

「你不觉得很有趣吗？左边是无穷数列的和，有无限个项，而且还无法全部写出来。可是相对的，右边却只有一个分数，无数项的和竟然以一个分数表现就可以了，这不是简洁到令人愉快吗？」

◎◎◎

……窗外已经渐渐暗了下来，图书室里只剩下我和米尔迦，米尔迦似乎是兴致来了，不等我回答就接着说：「接下来就继续朝生成函数前进吧。」

4．1．4迈向生成函数

「接下来就继续朝生成函数前进吧。」

以后就省略了收敛的条件，首先将刚才等比级数的无穷级数当成x的函数思考。

1＋x＋x<平方>＋x<立方>＋……

在这里为了要让此函数的n次系数更明显，所以将系数写出来。

1x<0次方>＋1x<1次方>＋1x<平方>＋1x<立方>＋……

像这样，各系数就形成了1，1，1，1，……的无穷数列，接下来的对应是……

数列←→函数

1，1，1，1，……←→1＋x＋x<平方>＋x<立方>＋……

也就是说，数列〈1，1，1，1，……〉与1＋x＋x<平方>＋x<立方>＋……函数可以当成是一样的，由于1＋x＋x<平方>＋x<立方>＋……＝1/(1－x)，所以将其如下置换。

数列←→函数

1，1，1，1，……←→1/(1－x)

这种数列与函数的对应可以如下广义化。

数列←→函数

〈a<0>，a<1>，a<2>，a<3>，……〉←→a<0>＋a<1>x＋a<2>x<平方>＋a<3>x<立方>＋……

这种与数列对应的函数称为生成函数，就是将分散的无数项集合成一个函数，生成函数即是x乘幂的无限和，也就是被定义为幂级数……

◎◎◎

……说到这里，米尔迦意外地安静下来，她像在思索似地保持沉默闭上双眼、缓缓地呼吸。

为了不打扰她，我只是在一旁静静地看着，看着她嘴唇美好的曲线、数列与对应的函数、金属框的眼镜、等比数列的无穷级数……以及生成函数。

米尔迦张开双眼。

「现在是在思考数列与对应的生成函数……吧？」米尔迦以温柔和缓的声音说着，」若是能求出生成函数的闭公式，则此闭公式也会与数列对应。」

「所以我稍微想了一下……」她说着说着，声音也像是在透露不能被别人知道的宝藏场所一样渐渐变小，并将脸靠近我，可以闻到她身上淡淡的橘子香。

「从现在开始，要在两个国度间来回奔跑。」米尔迦细语。

为了不听漏这些秘密的话语，我竖起耳朵，不过……两个国度？

「我想抓住数列，但是要直接抓住是很困难的，这时候就要从『数列的国度』到『生成函数的国度』，之后再回到『数列的国度』，这样或许就能抓到数列……」

「现在是闭校时间。」

突如其来的声音让我们都吓了一跳，凑在一起专心讨论的我们完全没有注意到图书管理员瑞谷老师站在我们身后。

※※数列与生成函数的对应

数列←→函数

〈a<0>，a<1>，a<2>，a<3>，……〉←→a<0>＋a<1>x＋a<2>x<平方>＋a<3>x<立方>＋……

4．2抓住斐波那契数列

这是我们往附近的饮料店移动，点了饮料后继续数列的话题，「抓住数列？什么意思？两个国度又是什么？」对于我的疑问，米尔迦用手扶正眼镜，说了声「是啊」后开始讲解。

4．2．1斐波那契数列

「是啊，这比喻是稍微异想天开了点。『在两个国度间来回抓住数列』就是『使用生成函数求出数列的一般项』的意思。」

现在来看看旅行地图吧，首先先求与数列对应的生成函数，再来将生成函数变形做出闭公式，然后将闭公式以幂级数展开求取数列的一般项，也就是说，经由生成函数可以发现数列的一般项。

※※『使用生成函数求出数列的一般项』的旅行地图

数列→生成函数

↓

数列的一般项←生成函数的闭公式

那么就以典型的斐波那契数列来思考，你知道斐波那契数列吧。

{0，1，1，2，3，5，8，……}

这是将临接的两项相加而得到下一个数的数列。

0，1，0＋1＝1，1＋1＝2，1＋2＝3，2＋3＝5。3＋5＝8，……

虽然也有从1开始的情况，不过现在就从0开始。

将斐波那契数列的一般项设为F<n>F<0>等于0，F<1>等于1，当n≥2时，F<n>＝Fn－2＋F<n－1>，也就是说F<n>被定义为一种递推公式。

※※斐波那契数列的定义(递推公式)

F<n>＝0(n＝0)

F<n>＝1(n＝1)

F<n>＝Fn－2＋F<n－1>(n≥2)

这个定义能将斐波那契数列『相邻的两项相加而得到下一个数』的特性充分展现，而且如同F<0>，F<1>，F<2>，……一样，斐波那契数列可以用计算循序渐进算出答案，但是并无法表现出F<n>为『对n的闭公式』，也就是F<n>并不是直接使用n的式子，这就是我所说『未捕捉』的状态。

当问题是「斐波那契数列的第1000项为何？」时，就必须以F<0>＋F<1>求得F<2>，F<1>＋F<2>求得F<3>，持续计算到F<998>＋F<999>最后得出F<1000>，要用递推公式求斐波那契数列就必须经过n－1次的加法，这样太麻烦了，我希望能以F<n>表示『对n的闭公式』，『对n的闭公式』概略来讲就是『将已知的计算过程在有限的次数内组合而成的公式』。

我希望以F<1>表示『对n的闭公式』，来抓住斐波那契数列。

※※问题4－1

以斐波那契数列的一般项F<n>表示『对n的闭公式』。

4．2．2斐波那契数列的生成函数

那么，将斐波那契数列对应的生成函数当作F(x)，也就是说，对应关系如下：

数列←→生成函数

F<0>，F<1>，F<2>，F<3>，……F(x)

将F(x)的系数x<n>设为F<n>，可以具体地写成下列算式，这样我们就到了生成函数的国度了。

F(x)＝F<0>x<0次方>＋F<1>x<1次方>＋F<2>x<平方>＋F<3>x<立方>＋F<4>x<4次方>＋……

＝0x<0次方>＋1x<1次方>＋1x<平方>＋2x<立方>＋3x<4次方>＋……

＝x＋x<平方>＋2x<立方>＋3x<4次方>＋……

接着要调查函数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)＝……＋Fn－2－2x<n－2次方>＋F<n－1>x<n－1次方>＋F<n>x<n次方>＋……

虽然想将Fn－2跟F<n－1>相加，但是由于x的次数不同而无法相加，到底该怎么办？

◎◎◎

……米尔迦看向我。嗯，的确，x的次方不同的话就无法相加，数不同就无法整合，不过本来数列与生成函数的对应，就是要避免x的次数混淆吧？数列与生成函数要如何对应，真的会有这么有趣的事情发生吗？米尔迦马上说出『很简单』这句话。

4．2．3求闭公式

「很简单。」

x的次方不同的话，就将不是的部分补上x就好了，乘法在指数上就变成加法，也就是所谓的指数法则。

x<n－2次方>×x<平方>＝x<n－2+2次方>＝x<n次方>

将F<n－2>x<n－2次方>乘以x<平方>就会变成Fn－2x<n次方>，照下面算式就能全部整合成x<n次方>，为了方便整合，这里将1视为x<0次方>。

F<n－2>x<n－2次方>×x<2>＝F<n－2>x<n次方>

F<n－1>x<n－1次方>×x<1>＝F<n－1>x<n次方>

F<n－0>x<n－0次方>×x<0>＝F<n－0>x<n次方>

这样就能对函数F(x)使用斐波那契数列的递推公式了，分别观察F(x)乘以x<平方>，x<1次方>，x<0次方>的式子吧。

式子A：F(x)×x<平方>＝＋F<0>x<平方>＋F<1>x<立方>＋F<2>x<4次方>＋……

式子B：F(x)×x<1次方>＝＋F<0>x<1次方>＋F<1>x<平方>＋F<2>x<立方>＋F<3>x<4次方>＋……

式子C：F(x)×x<0次方>＝F<0>x<0次方>＋F<1>x<1次方>＋F<2>x<平方>＋F<3>x<立方>＋F<4>x<4次方>＋……

这样次方就整合了，展开式A，B，C进行接下来的计算，如此一来，同次方的系数就可以使用F(x)的递推公式。

式子A＋式子B－式子C

计算的时候，将左边如下处理。

(左边)＝F(x)×x<平方>＋F(x)×x<1次方>－F(x)×x<0次方>

＝F(x)×(x<平方>＋x<1次方>－x<0次方>)

然后右边如下。

(右边)＝F<0>x<1>－F<0>x<0次方>－F<1>x<1次方>

＋(F<0>＋F<1>－F<2>)×x<平方>

＋(F<1>＋F<2>－F<3>)×x<立方>

＋(F<2>＋F<3>－F<4>)×x<4次方>

＋………………

＋(F<n－2>＋F<n－1>－F<n>)×x<n次方>

＋……

右边留下一开始的F<0>x<1次方>－F<0>x<0次方>－F<1>x<1次方>，其它会被全部消去，这是因为依照斐波那契数列的递推公式，F<0>x<1次方>－F<0>x<0次方>－F<1>x<1次方>会等于0。可以爽快地将它们消掉。

已经不需要用x<0次方>或x<1次方>这种麻烦的写法了，回到1与x，然后用F<0>＝0与F<1>＝1代入，会得到下列式子。

F(x)×(x<平方>＋x－1)＝－x

将两边同除x<平方>＋x－1后整理，就得到F(x)的闭公式，这就是F(x)的模样。

F(x)＝x/(1－x－x<平方>)

斐波那契数列的生成函数可以变成如此单纯的闭公式真是令人愉快，毕竟这个算式中可是包含了无限延伸的斐波那契数列，很简洁吧。

0，1，1，2，3，5，8，……←→x/(1－x－x<平方>)

※※斐波那契数列的生成函数F(x)的闭公式

F(x)＝x/(1－x－x<平方>)

4．2．4用无穷级数表示

接下来我们思考斐波那契数列的生成函数F(x)，将F(x)的闭公式以x的无穷级数表示的话，其n次的系数应该就会变成Fn。

「所以说，下一个目标就是将下式以x的无穷级数表现。

x/(1－x－x<平方>)

我们之前曾将分数形式的下式化成x的无穷级数。

1/(1－x)＝1＋x＋x<平方>＋x<立方>＋……

所以，是否能将x/(1－x－x<平方>)化成与1/(1－x)类似的形式呢？假如可以的话，我们就能从生成函数的国度回到数列的国度了，还会带着斐波那契数列的一般项当作土产，到底有没有办法呢？」

◎◎◎

……米尔迦偷偷往我看来。对了，再来将生成函数F(x)以无穷函数的形式表示的话，就能得到斐波那契数列的一般项吧，我专注在生成函数的形式上，想将它的构造看透。

F(x)＝x/(1－x－x<平方>)

分母1－x－x<平方>为二次式，总之先将1－x－x<平方>因式分解看看，我开始在笔记本上计算，米尔迦只是看着我动笔。

假设未知的定数r，s，可将1－x－x<平方>如下因式分解。

1－x－x<平方>＝(1－rx)(1－sx)

当如上因式分解后，就可以如下让分数和在通分时，刚好使分母为1－x－x<平方>。

1/(1+rx)+1/(1－sx)=某数/(1－rx)(1－sx)

=某数/(1－x－x<平方>)

为了让此计算式等于x/(1－x－x<平方>)，就必须决定r，s，来试着计算看看。

1/(1+rx)+1/(1－sx)＝(1－sx)/(1－rx)(1－sx)+(1－rx)/(1－rx)(1－sx)

＝(2－(r+s)x)/(1－(r+s)x+rsx<平方>)

嗯，好好选择r，s的话，分母1－(r＋s)x＋rsx<平方>这边似乎可以变成1－x－x<平方>，但是分子2－(r＋s)x的部分无法变成x，原因是常数项的2无法消掉。虽然很可惜，然而还是不行，真遗憾……

在我低喃的同时，米尔迦却说出『这样的话，之后就没问题了』这句话。

4．2．5解决

「这样的话，之后就没问题了。」

将分子也代入参数，也就是说，代入R，S，r，s这4个未知常数形成一列式……

R/(1－rx)+S/(1－sx)

然后计算。

R/(1－rx)+S/(1－sx)＝R(1－sx)/(1－rx)(1－sx)+S(1－rx)/(1－rx)(1－sx)

＝((R+S)－(rR+sS)x)/(1－(r+s)x+rsx<平方>)

为了让下式成立，要决定R，S，r，s这4个常数。

((R+S)－(rR+sS)x)/(1－(r+s)x+rsx<平方>)＝x/(1－x－x<平方>)

比较两边结构，会发现只需要解出以下的联立方程式即可。

R＋S＝0

rS＋sR＝－1

r＋s＝1

rs＝－1

有四个未知定数与四个独立的式子，试着解出这个联立方程式吧，只剩下动手了。

首先将R与S以r与s表示。

R＝1/(r－s)，S＝－1/(r－s)

这样就快得到将F(x)以无穷函数的形式表示的方法了，为了之后能求出r。s必须继续算下去。

F(x)＝x/(1－x－x<平方>)

＝x/(1－rx)(1－sx)

＝R/(1－rx)+S/(1－sx)

在这里带入R＝1/(r－s)，S＝－1/(r－s)

＝(1/(r－s))(1/(1－rx))－(1/(r－s))(1/(1－sx))

＝(1/(r－s))(1/(1－rx)－1/(1－sx))

然后这里用＝1＋rx＋r<平方>x<平方>＋r<立方>x<立方>＋……跟＝1＋sx＋s<平方>x<平方>＋s<立方>x<立方>＋……

＝(1/(r－s))((1＋rx＋r<平方>x<平方>＋r<立方>x<立方>＋……)－(1/(r－s))(1＋sx＋s<平方>x<平方>＋s<立方>x<立方>＋……))

＝(1/(r－s))((r－s)x＋(r<平方>－s<平方>)x<平方>＋(r<立方>－s<立方>)x<平方>＋……)

＝((r－s)/(r－s))x+((r<平方>－s<平方>)/(r－s))x<平方>＋((r<立方>－s<立方>)/(r－s))x<立方>＋……

整理之后就变成这样。

F(x)＝0＋((r－s)/(r－s))x+((r<平方>－s<平方>)/(r－s))x<平方>＋((r<立方>－s<立方>)/(r－s))x<立方>＋……

F0F1F2F3

这样就能将斐波那契数列的一般项以r，s表示。

F<n>＝(r<n次方>－s<n次方>)/(r－s)

之后就剩求出r，s了，r与s的联立方程式如下：

r＋s＝1

rs＝－1

要以一般解联立方程式的方式来解也可以，但是和为1且积为－1的两个数r，s，会等于方程x2－(r＋s)＋rs＝0的解，也就是所谓的「二次方程式的解与系数的关系」，理由则是由于下面的因式分解：

x<平方>－(r＋s)＋rs＝(x－r)(x－s)

也就是说，从r＋s＝1，rs＝－1，可以得到x＝r，s为以下方程序的解。

x<平方>－(r＋s)x＋rs＝x<平方>－x－1

＝0

利用二次方程式解的公式，可以得到以下结果。

x＝(1±<根号5>)/2

假定r＞s，则……

r＝(1＋<根号5>)/2

s＝(1－<根号5>)/2

而r－s＝<根号5>，所以……

(r<n次方>－s<n次方>)/(r－s)=(1/<根号5>)(((1＋<根号5>)/2)<n次方>-((1－<根号5>)/2)<n次方>)

可以得到斐波那契数列一般项F<n>如下。

F<n>＝(1/<根号5>)(((1＋<根号5>)/2)<n次方>-((1－<根号5>)/2)<n次方>)

好，这样就解决了。

※※解答4－1(斐波那契数列的一般项)

F<n>＝(1/<根号5>)(((1＋<根号5>)/2)<n次方>-((1－<根号5>)/2)<n次方>)

4．3回顾

……我还是无法接受，真的是这个答案吗？毕竟斐波那契数列全部都是整数，我不认为一般项会出现<根号5>。

脸上浮现满足表情的米尔迦一口气将已经变凉的咖啡喝完，对于我的疑问则是回答：「要试试看吗？」

那么，就以n＝0，1，2，3，4为例来验算。

F<0>＝(1/<根号5>)(((1＋<根号5>)/2)<0次方>-((1－<根号5>)/2)<0次方>)＝0/<根号5>＝0

F<1>＝(1/<根号5>)(((1＋<根号5>)/2)<1次方>-((1－<根号5>)/2)<1次方>)＝<根号5>/<根号5>＝1

F<2>＝(1/<根号5>)(((1＋<根号5>)/2)<平方>-((1－<根号5>)/2)<平方>)＝4<根号5>/4<根号5>＝1

F<3>＝(1/<根号5>)(((1＋<根号5>)/2)<立方>-((1－<根号5>)/2)<立方>)＝16<根号5>/8<根号5>＝2

F<4>＝(1/<根号5>)(((1＋<根号5>)/2)<4次方>-((1－<根号5>)/2)<4次方>)＝48<根号5>/16<根号5>＝3

0，1，1，2，3，确实是斐波那契数列。喔～～原来如此，实际计算的时候，分子跟分母会同时将<根号5>消掉啊！！

嗯，真厉害，我一边喝着咖啡，一边回顾今天的整个流程，想我们求出斐波那契数列的一般项(也就是对n的闭公式)，为此依着以下的顺序前进。

(1)思考与斐波那契数列的Fn的系数有关的生成函数F(x)。

(2)求函数F(x)的闭公式(在这里为对x的闭公式)，这里使用了斐波那契数列的递推公式。

(3)将函数F(x)的闭公式以无穷级数的形式表示，这时候的系数xn为斐波那契数列的一般项。

也就是说，使用与数列系数相同的函数——生成函数一一来『抓到数列』了，原来如此……不过，还真是漫长的旅途啊。

※※『求斐波那契数列的一般项』旅行地图

斐波那契数列→生成函数F(x)

↓

斐波那契数列一般项←生成函数F(x)的闭公式

接着米尔迦开始说：「生成函数是操作数列的有效方法。原因在于，我们熟知的函数解析方法都能在生成函数的国度里发挥效用，而在函数中培养的技术也能活用在数列的研究中。」

我边听着米尔迦说话，边担心别的事情。在计算无穷级数的时候，变更和的顺序不是不太好吗？米尔迦……这真的没问题吗？

「不清楚说明条件的话确实不好，不过这次就不要计较了，把使用生成函数发现的东西当成秘密，改用数学归纳法证明得出的一般项不就可以了。」

米尔迦爽快地回答。

……在展开长长的算式时，

使用生成函数这个重要的手段，

是为了要表示最初找出这个等式的方法，

——高德纳『TheArtofComputerProgramming』[22]