斐波那契数列

公元 1202 年，商人出身的意大利数学家斐波那契（Fi－bonacci，1170～ 1250），完成了一部伟大的论著《算法之书》。在书中，提出以下有趣问题：

假定一对刚出生的小兔一个月后就能长成大兔，再过一个月便能生下一对小兔，并且此后每个月都生一对小兔。一年内没有发生死亡，问一对刚出生的兔子，一年内繁殖成多少对兔子？逐月推算，我们可以得到前面提过的数列：

1，1，2，3，5，8，13，21，34，55，89，144，233。这个数列后来便以斐波那契的名字命名。数列的每一项，则称为“斐波那契数。”第十三位的斐波那契数，即为一对刚出一的小兔，一年内所能繁殖成的兔子的对数， 这个数字为 233。

从斐波那契数的构造明显看出：斐波那契数列从第三项起，每项都等于前面两项的和。假定第 n 项斐波那契数为 un，于是我们有：

u1 = u2 = 1

(n≥2)

u = u + u

 n+1 n n-1

通过以上的递推关系式，我们可以算出任何的 un，不过，当 n 很大时递推是很费事的，我们必须找到更为科学的计算方法！

下面我们就从等比数列

1，q，q2，q3，qn-1，⋯

中寻求满足递推关系 un+1=un+un-1 的解答。令 qn＝qn-1qn－2（n≥2）

因 q≠0 解得：

1 + 5

q1 = 2

1 − 5

q 2 = 2

un = αq1n−1 + βq2 n−1

现令u = u = 1

 1 2

α + β = 1

立知

α( ) + β(

) = 1





α =



解得

2 2

1 1 + 5

( 2 )

β = −



(1 − 5 ) 2

从而u =

1 + 5 ) n − (1 − 5 ) n ]

_n [( 2 2

以上公式是法国数学家比内首先证明的，通称比内公式。令人惊奇的是， 比内公式中的 un 是以无理数的幂表示的，然而这所得的结果完全是整数。不信，读者可以找几个 n 的值代进去试试看！

斐波那契数列有许多奇妙的性质，其中有一个性质是这样的：

u² －u n+1·u n-1 = （ - 1） ⁿ⁺¹（n＞1）

斐波那契数列的上述性质，常被用来构造一些极为有趣的智力游戏。美国《科学美国人》杂志就曾刊载过一则故事：

一位魔术师拿着一块边长为 13 英尺的正方形地毯，对他的地毯匠朋友

说：“请您把这块地毯分成四小块，再把它们缝成一块长 21 英尺，宽 8 英尺的长方形地毯。”这位匠师对魔术师算术之差，深感惊异。因

为两者之间面积相差达一平方英尺哩！可是魔术师竟让匠师用右图和下图的

方法，达到了他的目的！这真是不可思议！亲爱的读者，你猜猜那神奇的一

平方英尺跑到哪儿去呢？