恒邦物流邮政:有谁听说过PHI数列？

斐波那契数列
维基百科，自由的百科全书
(重定向自斐波那契数)
跳转到： 导航, 搜索
以斐波那契数为边的正方形拼成的长方形
放大
以斐波那契数为边的正方形拼成的长方形

斐波那契数列，英文为Fibonacci Number，台湾翻为费伯纳西数列。

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

* F0 = 0
* F1 = 1
* Fn = Fn - 1 + Fn - 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
目录
[隐藏]

* 1 源起
* 2 表达式
o 2.1 线性代数解法
o 2.2 近似值
o 2.3 用计算机求解
* 3 和黄金分割的关系
* 4 恒等式
* 5 相关的数列
o 5.1 和卢卡斯数列的关系
o 5.2 反斐波那契数列
o 5.3 巴都万数列
* 6 应用
* 7 参考
* 8 参见

[编辑]

源起

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

* 第一个月有一对刚诞生的兔子
* 第两个月之后它们可以生育
* 每月每对可生育的兔子会诞生下一对新兔子
* 兔子永不死去

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

[编辑]

表达式

为求得斐波那契数列的一般表达式，可以借助线性代数的方法。
[编辑]

线性代数解法

1 首先构建一个矩阵方程

设Jn为第n个月新出生的兔子数量，An为这一月份的兔子数量。

{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} \cdot {J_n\choose A_{n}},

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

2 求矩阵的特征值: λ

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

当行列式的值为0，解得λ1=\frac{1}{2} (1 + \sqrt{5}) 或 λ2=\frac{1}{2} (1 - \sqrt{5})

3 特征向量

将两个特征值代入

(\begin{pmatrix}0&1\\1&1\end{pmatrix}-\lambda \cdot E) \cdot\vec x = 0

求特征向量\vec x 得

\vec x_1=\begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}

\vec x_2=\begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}

4 分解首向量

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

{J_{1}\choose A_{1}} = \begin{pmatrix}0\\1\end{pmatrix}

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

\begin{pmatrix}0\\1\end{pmatrix}=\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}-\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix} （4）

5 用数学归纳法证明

从

{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} \cdot {J_n\choose A_{n}}=\lambda \cdot {J_n\choose A_{n}}

可得

{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix}^n \cdot {J_{1}\choose A_{1}} =\lambda^n \cdot {J_{1}\choose A_{1}} （5）

6 化简矩阵方程

将（4） 代入 （5）

{J_{n+1}\choose A_{n+1}} = \lambda^n \cdot [\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}-\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}]

根据 3

{J_{n+1}\choose A_{n+1}} = \frac{1}{\sqrt{5}} \cdot \lambda_1^n \cdot \begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}- \frac{1}{\sqrt{5}} \cdot \lambda_2^n\cdot \begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}

7 求A的表达式

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

A_{n+1}=\frac{1}{\sqrt{5}} \cdot \lambda_1^{n+1} - \frac{1}{\sqrt{5}} \cdot \lambda_2^{n+1}

A_{n+1}=\frac{1}{\sqrt{5}} \cdot (\lambda_1^{n+1} - \lambda_2^{n+1})

A_{n+1}=\frac{1}{\sqrt{5}} \cdot ((\frac{1}{2} (1 + \sqrt{5}))^{n+1} - (\frac{1}{2} (1 - \sqrt{5}))^{n+1}) (7)

(7)即为An+1 的表达式
[编辑]

近似值

F_n \approx \frac{1}{\sqrt{5}} a^n = \frac{1}{\sqrt{5}} \cdot ( \frac{1}{2} (1 + \sqrt{5}) )^n \approx 0,223606798 \cdot 3,236067977^n

[编辑]

用计算机求解

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

可通过递归的算法解决此两个问题。
[编辑]

和黄金分割的关系

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

\frac {f_{n+1}}{f_n} \approx a = \frac{1}{2} (1 + \sqrt{5}) = \Phi \approx 1{,}618{...}

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

\frac{1}{1} = 1 \qquad \frac{2}{1} = 1+\frac{1}{1} \qquad \frac{3}{2} = 1+\frac{1}{1+ \frac{1}{1}} \qquad \frac{5}{3} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1}}} \qquad \frac{8}{5} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1}}}}

F_n = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\} = {\phi^n \over \sqrt{5}} - {(1-\phi)^n \over \sqrt{5}}

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

\Phi = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1+ ...}}}}

[编辑]

恒等式

证明以下的恒等式有很多方法。以下会用组合论述来证明。Fn可以表示成用多个1和多个2相加令其和等于n-1的方法的数目。例如F0 = 0，表示没有方法可以加到0。在这里加的过程中，先后次序不同但使用1和使用2的数目一样的两个方法视为不同。例如 1+1+2 和 2+1+1 是两个不同的方法。

* Fn + 1 = Fn + Fn − 1

不失一般性，我们假设n ≥ 1。Fn + 1是计算了将1和2加到n的方法的数目。若第一个被加数是1，有Fn种方法来完成对n-1的计算；若第一个被加数是2，有F(n-1)来完成对n-2的计算。因此，共有Fn + Fn - 1种方法来计算n的值。

* F1 + F2 + F3 + ... + Fn = Fn + 2 - 1

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

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

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

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

* F1 + 2F2 + 3F3 + ... + nFn = nFn + 2 - Fn + 3 + 2

* F1 + F3 + F5 + ... + F2n - 1 = F2n
* F2 + F4 + F6 + ... + F2n = F2n + 1 - 1
* {F_1}^2 + {F_2}^2 + {F_3}^2 + ... + {F_n}^2 = F_n F_{n+1}
* F_{n-1} F_{n+1} - {F_n}^2 = (-1)^n

[编辑]

相关的数列

斐波那契数列是卢卡斯数列的特殊情况。或是斐波那契n步数列步数为2的情形。
[编辑]

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

反斐波那契数列

反斐波那契数列的递归公式如下：

Gn + 2 = Gn − Gn + 1

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

即是F_{2n+1} = G_{2n+1}，F_{2n} = - G_{2n}。

反斐波那契数列两项之间的比会趋近-\frac{1}{\phi}=-0.618。
[编辑]

巴都万数列

斐波那契数列可以用一个接一个的正方形来表现，巴都万数列则是用一个接一个的等边三角形来表现，它有Pn + 2 = Pn − 2 + Pn − 3的关系。
[编辑]

应用
[编辑]

参考

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

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

* 本页的英语、德语和日语版本

[编辑]

参见

* 首五百个斐波那契数
* 齐肯多夫定理

取自"http://wikipedia.cnblog.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97"

Category: 整数数列