斐波那契数列

维基百科,自由的百科全书
跳转至: 导航搜索
以費波那西數為邊的正方形拼成的長方形

費波那契數列意大利语:Successione di Fibonacci),又譯費波拿契數斐波那契數列費氏數列黃金分割數列

數學上,費波那契數列是以遞歸的方法來定義:

  • F_0=0
  • F_1=1
  • F_n = F_{n-1}+ F_{n-2}(n≧2)

用文字來說,就是費波那契數列由0和1開始,之後的費波那契系數就由之前的兩數相加。首幾個費波那契系數是(OEISA000045):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

特別指出0不是第一項,而是第零項。

源起[编辑]

根據高德納(Donald Ervin Knuth)的《計算機程序設計藝術》(The Art of Computer Programming),1150年印度數學家Gopala金月在研究箱子包裝物件長闊剛好為1和2的可行方法數目時,首先描述這個數列。 在西方,最先研究這個數列的人是比薩的李奧納多(又名費波那西),他描述兔子生長的數目時用上了這數列。

  • 第一個月初有一對剛誕生的兔子
  • 第二個月之後(第三個月初)牠們可以生育
  • 每月每對可生育的兔子會誕生下一對新兔子
  • 兔子永不死去

假設在n月有可生育的兔子總共a對,n+1月就總共有b對。在n+2月必定總共有a+b對: 因為在n+2月的時候,前一月(n+1月)的b對兔子可以存留至第n+2月(在當月屬於新誕生的兔子尚不能生育)。而新生育出的兔子對數等於所有在n月就已存在的a對

表達式[编辑]

為求得斐波那契數列的一般表達式,可以藉助線性代數的方法。高中的初等數學知識也能求出。

初等代數解法[编辑]

已知

  • a_1=1
  • a_2=1
  • a_n = a_{n-1}+ a_{n-2}

首先構建等比數列[编辑]

a_n +\alpha a_{n-1}=\beta (a_{n-1}+\alpha  a_{n-2})
化簡得
a_n=(\beta -\alpha) a_{n-1}+ \alpha\beta a_{n-2}
比較系數可得:
 \begin{cases}
\beta-\alpha=1 \\
\alpha\beta=1
\end{cases}
不妨設\beta>0,  \alpha>0
解得:

 \begin{cases}
\alpha=\dfrac{\sqrt{5}-1}{2} \\
\beta=\dfrac{\sqrt{5}+1}{2}
\end{cases}
所以有a_n +\alpha a_{n-1}=\beta (a_{n-1}+\alpha  a_{n-2}), 即\left\{a_n +\alpha a_{n-1}\right\}為等比數列。

求出數列{a_n +\alpha a_{n-1}}[编辑]

由以上可得:
\begin{align}a_{n+1} +\alpha a_{n} &=(a_2+\alpha a_1)\beta^{n-1}\\
& = (1+\alpha)\beta^{n-1}\\
& =\beta^n \\
\end{align}

變形得: \frac{a_{n+1}}{\beta^{n+1}}+\frac{\alpha}{\beta}\frac{a_{n}}{\beta^{n}}=\frac{1}{\beta}。 令b_n=\frac{a_n}{\beta^n}

求數列{b_n}進而得到{a_n}[编辑]

b_{n+1}+\frac{\alpha}{\beta}b_{n}=\frac{1}{\beta}
b_{n+1}+\lambda=-\frac{\alpha}{\beta} (b_{n}+\lambda),解得\lambda=-\frac{1}{\alpha+\beta}。 故數列\left\{b_n+\lambda\right\}為等比數列
b_n+\lambda=\left(-\frac{\alpha}{\beta}\right)^{n-1}\left(b_1+\lambda\right)。而b_1=\frac{a_1}{\beta}=\frac{1}{\beta}, 故有b_n+\lambda=\left(-\frac{\alpha}{\beta}\right)^{n-1}\left(\frac{1}{\beta}+\lambda\right)
又有 \begin{cases}
\alpha=\dfrac{\sqrt{5}-1}{2} \\
\beta=\dfrac{\sqrt{5}+1}{2}
\end{cases}b_n=\frac{a_n}{\beta^n}
可得a_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]

得出{a_n}表達式

a_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]

線性代數解法[编辑]


\begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix}
=
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix}


\begin{pmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n} \end{pmatrix}
=
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n + 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的表達式。

求矩陣的特徵值 \lambda [编辑]

行列式:- \lambda *(1- \lambda )-1*1= \lambda 2- \lambda -1

當行列式的值為0,解得 \lambda_1 =\frac{1}{2} (1 + \sqrt{5}) \lambda_2 =\frac{1}{2} (1 - \sqrt{5})

特徵向量[编辑]

將兩個特徵值代入

\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}

分解首向量[编辑]

第一個月的情況是兔子一對,新生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)

數學歸納法證明[编辑]

{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)

化簡矩陣方程[编辑]

將(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}

求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=\sum_{i=0}^{\infty} \binom {n-i}{i}[1]

 F_{n-1}+F_n=\sum_{i=0}^{\infty} \binom {n-1-i}{i}+\sum_{i=0}^{\infty} \binom {n-i}{i}=1+\sum_{i=1}^{\infty} \binom {n-i}{i-1}+\sum_{i=1}^{\infty} \binom {n-i}{i}=1+\sum_{i=1}^{\infty} \binom {n+1-i}{i}=\sum_{i=0}^{\infty} \binom {n+1-i}{i}=F_{n+1}

近似值[编辑]

F_n \approx \frac{1}{\sqrt{5}} a^n = \frac{1}{\sqrt{5}} \cdot ( \frac{1}{2} (1 + \sqrt{5}) )^n \approx 0.4472135955 \cdot 1.618033988745^n

用計算機求解[编辑]

可通過編程觀察斐波那契數列。分為兩類問題,一種已知數列中的某一項,求序數。第二種是已知序數,求該項的值。

可通過遞歸遞推的算法解決此兩個問題。 事實上當n相當巨大的時候,O(n)的遞推/遞歸非常慢……這時候要用到矩陣加速這一技巧。

和黃金分割的關係[编辑]

開普勒發現數列前、後兩項之比1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ,...... ,也組成了一個數列,會趨近黃金分割

\frac {f_{n+1}}{f_n} \approx a = \frac{1}{2} (1 + \sqrt{5}) = \varphi \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\} = {\varphi^n \over \sqrt{5}} - {(1-\varphi)^n \over \sqrt{5}}

而黃金分割數亦可以用無限連分數表示:

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

和自然的關係[编辑]

許多的生物構成都和斐波那契數列有正相關。例如人體脚底至頭頂之距離和從肚臍至腳底之距趨近\lim_{n \to \infty}\frac{F_n}{F_{(n-1)}} ,向日葵種子螺旋排列99%F_n

恆等式[编辑]

證明以下的恆等式有很多方法。以下會用組合論述來證明。F_n可以表示成用多個1和多個2相加令其和等於F_{n-1} + F_{n-2}不失一般性,我們假設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_0 + F_1 + F_2 + F_3 + ... + 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_0為要求的數目。

  • F_1 + 2 F_2 + 3 F_3 + ... + n F_n = n F_{n + 2} - F_{n + 3} + 2
  • F_1 + F_3 + F_5 + ... + F_{2n-1} = F_{2n}
  • F_2 + F_4 + F_6 + ... + F_{2n} = F_{2n+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的特殊情況,也和盧卡斯數列有關。

和盧卡斯數列的關係[编辑]

反費波那西數列[编辑]

反費波那西數列的遞歸公式如下:

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}

費波那西數列兩項之間的比會趨近-\frac{1}{\varphi}=-0.618

巴都萬數列[编辑]

費波那西數列可以用一個接一個的正方形來表現,巴都萬數列則是用一個接一個的等邊三角形來表現,它有P_{n} = P_{n-2} + P_{n-3}的關係。

循環數列[编辑]

cn+2=cn+1-cn 設首項為0,第二項為X,則形成數列0,X,X,0,-X,-X,0,X,X,0,-X,-X。呈現六個為一組的循環。

應用[编辑]

1970年,尤裏·馬季亞謝維奇指出了偶角標的斐波那契函數

 y = F_{2x}

正是滿足Julia Robison假設的丟番圖函數,因而證明了希爾伯特第十問題是不可解的。

相關猜想[编辑]

斐波那契數列中是否存在無窮多個質數?

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

程式參考[编辑]

function fib(n) {
    var fib_n = function(curr, next, n) {
        if (n == 0) {
            return curr;
        } else {
            return fib_n(next, curr+next, n-1);
        }
    }
    return fib_n(0, 1, n);
}
alert(fib(40));

參考文獻[编辑]

  • KNUTH, D. E. 1997. The Art of Computer ProgrammingArt of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley. Chapter 1.2.8.
  • 克裏福德A皮科夫.數學之戀.湖南科技出版社.
  1. ^ 斐波那契数列与组合数的一个关系及推广. 

參見[编辑]

外部連結[编辑]