費氏數列

費氏數列[編輯]

本條目需要補充更多來源。（2014年3月25日）  請協助添加多方面可靠來源以改善這篇條目，無法查證的內容可能會被提出異議而移除。

以費波那西數為邊的正方形拼成的長方形

費波那契數列（義大利語：Successione di Fibonacci），又譯費波拿契數、費氏數列、費氏數列、黃金分割數列。

在數學上，費波那契數列是以遞迴的方法來定義：

• F0=0
• F1=1
• Fn=Fn−1+Fn−2(n≧2)

用文字來說，就是費波那契數列由0和1開始，之後的費波那契係數就由之前的兩數相加。首幾個費波那契係數是（ A000045）：

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

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

目錄

  [隱藏] 

• 1 源起
• 2 表達式
  • 2.1 初等代數解法
    • 2.1.1 首先構建等比數列
    • 2.1.2 求出數列{}
    • 2.1.3 求數列{}進而得到{}
  • 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 近似值
  • 2.5 用計算機求解
• 3 和黃金分割的關係
• 4 和自然的關係
• 5 恆等式
• 6 相關的數列
  • 6.1 和盧卡斯數列的關係
  • 6.2 反費波那西數列
  • 6.3 巴都萬數列
  • 6.4 循環數列
• 7 應用
• 8 相關猜想
• 9 程式參考
• 10 參考文獻
• 11 參見
• 12 外部連結

源起[編輯]

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

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

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

表達式[編輯]

為求得費氏數列的一般表達式，可以藉助線性代數的方法。高中的初等數學知識也能求出。

初等代數解法[編輯]

已知

• a1=1
• a2=1
• an=an−1+an−2

首先構建等比數列[編輯]

設an+αan−1=β(an−1+αan−2)
化簡得
an=(β−α)an−1+αβan−2
比較係數可得：
{β−α=1αβ=1
不妨設β>0,α>0
解得：

⎧⎩⎨⎪⎪⎪⎪α=5√−12β=5√+12
所以有an+αan−1=β(an−1+αan−2)， 即{an+αan−1}為等比數列。

求出數列{an+αan−1}[編輯]

由以上可得：
an+1+αan=(a2+αa1)βn−1=(1+α)βn−1=βn

變形得： an+1βn+1+αβanβn=1β。 令bn=anβn

求數列{bn}進而得到{an}[編輯]

bn+1+αβbn=1β
設bn+1+λ=−αβ(bn+λ)，解得λ=−1α+β。 故數列{bn+λ}為等比數列
即bn+λ=(−αβ)n−1(b1+λ)。而b1=a1β=1β， 故有bn+λ=(−αβ)n−1(1β+λ)
又有⎧⎩⎨⎪⎪⎪⎪α=5√−12β=5√+12 和bn=anβn
可得an=5√5⋅[(1+5√2)n−(1−5√2)n]

得出an表達式

an=5√5⋅⎡⎣(1+5√2)n−(1−5√2)n⎤⎦

線性代數解法[編輯]

(Fn+2Fn+1)=(1110)⋅(Fn+1Fn)

(Fn+2Fn+1Fn+1Fn)=(1110)n+1

構建一個矩陣方程[編輯]

設J_n為第n個月有生育能力的兔子數量，A_n為這一月份的兔子數量。

(Jn+1An+1)=(0111)⋅(JnAn),

上式表達了兩個月之間，兔子數目之間的關係。而要求的是，A_n+1的表達式。

求矩陣的特徵值：λ[編輯]

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

當行列式的值為0，解得λ1=12(1+5√)或λ2=12(1−5√)

特徵向量[編輯]

將兩個特徵值代入

(0111)−λ⋅E)⋅x→=0

求特徵向量x→得

x→1=(112(1+5√))

x→2=(112(1−5√))