维基百科，自由的百科全书

跳转到： 导航, 搜索

费波那西数列（Fibonacci Sequence），又译费波拿契数、斐波那契数列、费氏数列、黄金分割数列。

在数学上，费波那西数列是以递归的方法来定义：

• F₀ = 0
• F₁ = 1
• F_n = F_{n − 1} + F_{n − 2}

用文字来说，就是费波那西数列由 0 和 1 开始，之后的费波那西系数就由之前的两数相加。首几个费波那西系数是（OEIS A000045）：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，………………

特别指出：0不是第一项，而是第零项。

目录 [隐藏] 1 源起 2 表达式 2.1 初等代数解法 2.1.1 首先构建等比数列 2.1.2 求出数列{an + αan − 1} 2.1.3 求数列{bn}进而得到{an} 2.2 线性代数解法 2.2.1 构建一个矩阵方程 2.2.2 求矩阵的特征值：λ 2.2.3 特征矢量 2.2.4 分解首矢量 2.2.5 用数学归纳法证明 2.2.6 化简矩阵方程 2.2.7 求A的表达式 2.3 近似值 2.4 用计算机求解 3 和黄金分割的关系 4 和自然的关系 5 恒等式 6 相关的数列 6.1 和卢卡斯数列的关系 6.2 反费波那西数列 6.3 巴都万数列 7 应用 8 相关猜想 9 参考 10 参见 11 外部链接

[编辑] 源起

根据高德纳（Donald Ervin Knuth）的《计算机程序设计艺术》（The Art of Computer Programming），1150年印度数学家Gopala和金月在研究箱子包装物件长阔刚好为 1 和 2 的可行方法数目时，首先描述这个数列。 在西方，最先研究这个数列的人是比萨的列奥那多（又名费波那西），他描述兔子生长的数目时用上了这数列。

• 第一个月初有一对刚诞生的兔子
• 第二个月之后(第三个月初)它们可以生育
• 每月每对可生育的兔子会诞生下一对新兔子
• 兔子永不死去

假设在 n 月有新生及可生育的兔子总共 a 对，n+1 月就总共有 b 对。在 n+2 月必定总共有 a+b 对： 因为在 n+2 月的时候，所有在 n 月就已存在的 a 对兔子皆已可以生育并诞下 a 对后代；同时在前一月(n+1月)之 b 对兔子中，在当月属于新诞生的兔子尚不能生育。

[编辑] 表达式

为求得费波那西数列的一般表达式，可以借助线性代数的方法。高中的初等数学知识也能求出。

[编辑] 初等代数解法

已知

• a₁ = 1
• a₂ = 1
• a_n = a_{n − 1} + a_{n − 2}

[编辑] 首先构建等比数列

设a_n + αa_{n − 1} = β(a_{n − 1} + αa_{n − 2})
化简得
a_n = (β − α)a_{n − 1} + αβa_{n − 2}
比较系数可得:
http://upload.wikimedia.org/wikipedia/zh/math/4/e/e/4ee4698d16ae45349e6fd5252f80938a.png  维基百科" />
不妨设β > 0,α > 0
解得：

http://upload.wikimedia.org/wikipedia/zh/math/5/5/2/552792a9c6d1f041ef6d9a4a1f151e57.png  维基百科" />
所以有a_n + αa_{n − 1} = β(a_{n − 1} + αa_{n − 2})， 即http://upload.wikimedia.org/wikipedia/zh/math/0/7/a/07ae8d6e328356269fe4ce97a42eaab0.png  维基百科" />为等比数列。

[编辑] 求出数列{a_n + αa_{n − 1}}

由以上可得：
http://upload.wikimedia.org/wikipedia/zh/math/c/3/a/c3ad4bdf9ab8a95bcc012faecbc5ea59.png  维基百科" />

变形得： http://upload.wikimedia.org/wikipedia/zh/math/2/f/8/2f856deb15da64f37f895d7f9ae5a37a.png  维基百科" /> 。 令http://upload.wikimedia.org/wikipedia/zh/math/c/6/4/c645522d34e2788f70abee17375f1888.png  维基百科" />

[编辑] 求数列{b_n}进而得到{a_n}

http://upload.wikimedia.org/wikipedia/zh/math/1/c/d/1cd09de0ce6cd57cd07c5e753bdb2922.png  维基百科" />
设http://upload.wikimedia.org/wikipedia/zh/math/0/e/6/0e6009bab1d4dec0e4ec2783958e3e4e.png  维基百科" />。 故数列 http://upload.wikimedia.org/wikipedia/zh/math/f/e/4/fe44bffd9793b9e0d9de097668bcc296.png  维基百科" /> 为等比数列
即 http://upload.wikimedia.org/wikipedia/zh/math/e/5/d/e5d3869932e692eebef12ee0d3771246.png  维基百科" /> 。而 http://upload.wikimedia.org/wikipedia/zh/math/b/c/3/bc351578116e273eba47465053ca8710.png  维基百科" /> ， 故有 http://upload.wikimedia.org/wikipedia/zh/math/d/8/3/d839d79c5416ac6658571e5662f90dcb.png  维基百科" />
又有http://upload.wikimedia.org/wikipedia/zh/math/5/5/2/552792a9c6d1f041ef6d9a4a1f151e57.png  维基百科" /> 和 http://upload.wikimedia.org/wikipedia/zh/math/c/6/4/c645522d34e2788f70abee17375f1888.png  维基百科" />
可得 http://upload.wikimedia.org/wikipedia/zh/math/e/b/b/ebbc3dfc4c53d561ada6e5225de82e78.png  维基百科" />

得出 a_n 表达式

http://upload.wikimedia.org/wikipedia/zh/math/e/b/b/ebbc3dfc4c53d561ada6e5225de82e78.png  维基百科" />

[编辑] 线性代数解法

[编辑] 构建一个矩阵方程

设J_n为第n个月有生育能力的兔子数量，A_n为这一月份的兔子数量。

http://upload.wikimedia.org/wikipedia/zh/math/6/f/a/6fac5c2122b590c76aed21fe4c4e0448.png  维基百科" />

上式表达了两个月之间，兔子数目之间的关系。而要求的是，A_n+1的表达式。

[编辑] 求矩阵的特征值：λ

行列式：-λ*(1-λ)-1*1=λ2-λ-1

当行列式的值为0，解得λ₁=http://upload.wikimedia.org/wikipedia/zh/math/7/5/9/7599ba16c3c73f5d4f15deb783c06e44.png  维基百科" /> 或 λ₂=http://upload.wikimedia.org/wikipedia/zh/math/3/7/6/376bc070902f0482b57f27073c1aff36.png  维基百科" />

[编辑] 特征矢量

将两个特征值代入

http://upload.wikimedia.org/wikipedia/zh/math/a/c/4/ac49e403516507ba422d968095da8ca8.png  维基百科" />

求特征矢量http://upload.wikimedia.org/wikipedia/zh/math/2/d/8/2d840484ec0396a01d0673b82c4a306c.png  维基百科" /> 得

http://upload.wikimedia.org/wikipedia/zh/math/3/e/7/3e7a41153e1b739eb899b1b5ee5fa225.png  维基百科" />

http://upload.wikimedia.org/wikipedia/zh/math/8/6/f/86f7d3de7e3813d6ad927ef86b0e86b3.png  维基百科" />

[编辑] 分解首矢量

第一个月的情况是兔子一对，新生0对。

http://upload.wikimedia.org/wikipedia/zh/math/5/d/2/5d26f0b7c7f54dd45ad4d726fe76e92d.png  维基百科" />

将它分解为用特征矢量表示。

http://upload.wikimedia.org/wikipedia/zh/math/4/a/2/4a26ff5ffb020785f210d3dd1cbc6544.png  维基百科" /> （4）

[编辑] 用数学归纳法证明

从

http://upload.wikimedia.org/wikipedia/zh/math/b/1/3/b13715e6c661a962a873288fa7f0fd29.png  维基百科" />

可得

http://upload.wikimedia.org/wikipedia/zh/math/f/f/a/ffa30051b9a7e058fd17a5409bf07a0a.png  维基百科" /> （5）

[编辑] 化简矩阵方程

将（4） 代入 （5）

http://upload.wikimedia.org/wikipedia/zh/math/4/4/6/446d66dd22fa3aa2c6eeb0f88537af46.png  维基百科" />

根据 3

http://upload.wikimedia.org/wikipedia/zh/math/3/2/6/326dda8e104149f66a5baf270849f348.png  维基百科" />

[编辑] 求A的表达式

现在在6的基础上，可以很快求出A_n+1 的表达式，将两个特征值代入 6 中

http://upload.wikimedia.org/wikipedia/zh/math/0/9/e/09e5612dce812cde666ed18bf93e8641.png  维基百科" />

http://upload.wikimedia.org/wikipedia/zh/math/f/2/f/f2f3a68dfdf167a790618122bea06023.png  维基百科" />

http://upload.wikimedia.org/wikipedia/zh/math/8/6/f/86facc55958efc7607f8fae134220bed.png  维基百科" /> (7)

(7)即为A_n+1 的表达式

[编辑] 近似值

http://upload.wikimedia.org/wikipedia/zh/math/b/3/a/b3a5cea4f68d5417b54f7f9202f8c0aa.png  维基百科" />

[编辑] 用计算机求解

可通过编程观察斐波那契数列。分为两类问题，一种已知数列中的某一项，求序数。第二种是已知序数，求该项的值。

可通过递归递推的算法解决此两个问题。 事实上当n相当巨大的时候，O(n)的递推/递归非常慢……这时候要用到矩阵加速这一技巧。

[编辑] 和黄金分割的关系

开普勒发现两个斐波那契数的比会趋近黄金分割：

http://upload.wikimedia.org/wikipedia/zh/math/b/9/c/b9ca422ce4898bdf4ba6a99ef7f6cd17.png  维基百科" />

斐波那契数亦可以用连分数来表示：

http://upload.wikimedia.org/wikipedia/zh/math/5/e/c/5ec9e81a45182c04df3560660b6a9449.png  维基百科" />

http://upload.wikimedia.org/wikipedia/zh/math/a/5/2/a520578c8ec33a1712802109d9ccfef3.png  维基百科" />

而黄金分割数亦可以用无限连分数表示：

http://upload.wikimedia.org/wikipedia/zh/math/d/e/6/de6b96281fb8ff5ee3a5f5745bcf4a41.png  维基百科" />

[编辑] 和自然的关系

许多的生物构成都和斐波那契数列有正相关。例如人体从肚脐至头顶之距离和从肚脐至脚底之距趋近于http://upload.wikimedia.org/wikipedia/zh/math/f/7/3/f735c5839de8d9f57f6da97697b26141.png  维基百科" /> ,向日葵的种子螺旋排列99%是F_n。

[编辑] 恒等式

证明以下的恒等式有很多方法。以下会用组合论述来证明。F_n可以表示成用多个1和多个2相加令其和等于<mat 不失一般性，我们假设n ≥ 1。F_{n + 1}是计算了将1和2加到n的方法的数目。若第一个被加数是1，有F_n种方法来完成对n-1的计算；若第一个被加数是2，有F(n-1)来完成对n-2的计算。因此，共有F_n + F_{n − 1}种方法来计算n的值。

• F₁ + F₂ + F₃ + ... + F_n = F_{n + 2} − 1

计算用多个1和多个2相加令其和等于n+1的方法的数目，同时最后一个加数是2的情况。

如前所述，当n  0，有F_{n + 2}种这样的方法。因为当中只有一种方法不用使用2，就即 1 + 1 + ... + 1　（n+1项），于是我们从F_{n + 2}减去1。

1. 若第1个被加数是2，有F_n个方法来计算加至n-1的方法的数目；
2. 若第2个被加数是2、第1个被加数是1，有F_{n − 1}个方法来计算加至n − 2的方法的数目。
3. 重复以上动作。
4. 若第n + 1个被加数为2，它之前的被加数均为1，就有F(0)个方法来计算加至0的数目。

若该数式包含2为被加数，2的首次出现位置必然在第1和n+1的被加数之间。2在不同位置的情况都考虑到后，得出F_n + F_{n − 1} + ... + F₀为要求的数目。

• F₁ + 2F₂ + 3F₃ + ... + nF_n = nF_{n + 2} − F_{n + 3} + 2

• F₁ + F₃ + F₅ + ... + F_{2n − 1} = F_2n
• F₂ + F₄ + F₆ + ... + F_2n = F_{2n + 1} − 1
• http://upload.wikimedia.org/wikipedia/zh/math/9/d/e/9de260182cad362fcdebbac5e4dd2028.png  维基百科" />
• http://upload.wikimedia.org/wikipedia/zh/math/d/7/4/d74f4f0e323bab81047d942fb26b9f84.png  维基百科" />

[编辑] 相关的数列

费波那西数列是费波那西n步数列步数为2的特殊情况，也和卢卡斯数列有关。

[编辑] 和卢卡斯数列的关系

[编辑] 反费波那西数列

反费波那西数列的递归公式如下：

G_{n + 2} = G_n − G_{n + 1}

如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...

即是F_{2n + 1} = G_{2n + 1},F_2n = − G_2n。

反费波那西数列两项之间的比会趋近http://upload.wikimedia.org/wikipedia/zh/math/d/5/2/d52f707dd03889267d58198af7582a32.png  维基百科" />。

[编辑] 巴都万数列

费波那西数列可以用一个接一个的正方形来表现，巴都万数列则是用一个接一个的等边三角形来表现，它有P_n = P_{n − 2} + P_{n − 3}的关系。

[编辑] 应用

1970年，Yuri Matiyasevich 指出了偶角标的斐波那契函数

y = F_2x

正是满足 Julia Robison 假设的丢番图函数，因而证明了希尔伯特第十问题是不可解的。

[编辑] 相关猜想

斐波那契数列中是否存在无穷多个素数？

在斐波那契数列中，有素数： 2,3,5,13,89,233,1597,28657,514229,433494437,2971215073,99194853094755497,1066340417491710595814572169,19134702400093278081449423917…… 目前已知最大素数是第81839个斐波那契数，一共有17103位数。

[编辑] 参考

• Donald E. Knuth: THE ART OF COMPUTER PROGRAMMING Volume 1/Fundamental

Algorithms. 第一章第 1.2.8 节《斐波那契数》。

• 《数学之恋》【美】克利福德德A皮科夫著，湖南科技出版社