斐波那契数

-{zh-hant:費波那契數;zh-hans:斐波那契数}-（意大利语：Numero di Fibonacci），又譯為菲波拿契數、菲波那西數、斐氏數、黃金分割數、費氏數列。所形成的數列稱為-{zh-hant:費波那契數列;zh-hans:斐波那契数列}-（意大利语：Successione di Fibonacci），又譯為菲波拿契數列、菲波那西數列、斐氏數列、黃金分割數列、費氏數列。這個數列是由意大利數學家斐波那契在他的《算盤書》中提出。

在數學上，斐波那契數是以遞歸的方法來定義：

（）

用白話文來說，就是斐波那契數列由0和1開始，之後的斐波那契數就是由之前的兩數相加而得出。首幾個斐波那契數是：
987……

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

起源
公元1150年印度數學家Gopala和金月在研究箱子包裝物件長宽剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是比薩的李奧納多（意大利人斐波那契Leonardo Fibonacci, 1175－1250），他描述兔子生長的數目時用上了這數列：
第一個月初有一對剛誕生的兔子
第二個月之後（第三個月初）牠們可以生育
每月每對可生育的兔子會誕生下一對新兔子
兔子永不死去
假設在月有兔子總共對，月總共有對。在月必定總共有對：因為在月的時候，前一月（月）的對兔子可以存留至第月（在當月屬於新誕生的兔子尚不能生育）。而新生育出的兔子對數等於所有在月就已存在的對
斐波纳契数也是杨辉三角形（即帕斯卡三角形）的每一条红色对角线上数字的和。

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

（n≥3）

首先構建等比數列
設化簡得
比較係數可得：

不妨設
解得：

又因为有，
即為等比數列。

求出數列{an+αan-1}
由以上可得：

變形得：
。
令

 求數列{bn}進而得到{an}

設，解得。
故數列為等比數列
即。而，
故有
又有
和
可得

得出表達式，稱(Binet's Formula)

 用數學歸納法證明表達式 
證明，其中為黃金比例，為任意整數
若為非負整數
當時，，成立
當時，，成立
設當及時皆成立，即且
當時

亦成立
若為非正整數
當時，成立
當時，，成立
設當及時皆成立，即且
當時

亦成立

因此，根據數學歸納法原理，此表達式對於任意整數皆成立

線性代數解法

稱為「斐波那契Q矩陣」(Fibonacci Q-Matrix)
構建一個矩陣方程

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

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

求矩陣的特徵值：λ

根据特征值的计算公式，我们需要算出来  所对应的解。

展开行列式有：。

故當行列式的值為 0，解得  或 。

特徵向量
將兩個特徵值代入



求特徵向量得

=

=

分解首向量
第一個月的情況是兔子一對，新生0對。

將它分解為用特徵向量表示。

  （4）

用數學歸納法證明

從
=

可得到

  （5）

化簡矩陣方程

將（4） 代入 （5）

根據3

求A的表達式
現在在6的基礎上，可以很快求出的表達式，將兩個特徵值代入6中

（7）

（7）即為的表達式

 數論解法 
實際上，如果將斐波那契數列的通項公式寫成，即可利用解二階線性齊次遞迴關係式的方法，寫出其特徵多項式（該式和表達斐波那契數列的矩陣的特徵多項式一致），然後解出=，=，即有，其中为常数。我们知道，因此，解得。

組合數解法



黃金比例恆等式解法
設為黃金比例，則有恆等式與，其中為任意整數，則

因此得到的一般式：

此一般式對任意整數成立

近似值
當為足夠大的正整數時，则

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

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

和黃金分割的關係
開普勒發現數列前、後兩項之比，也組成了一個數列，會趨近黃金分割：

斐波那契數亦可以用連分數來表示：

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

而黃金分割數也可以用無限多重根號表示：

和自然的關係


斐氏數列見於不同的生物學現象，如樹的分枝、、菠蘿聚花果上小單果的排列、雅枝竹的花蕾、正在舒展的蕨葉、松毬的鱗的排列、蜜蜂的家族樹。开普勒曾指出斐氏數列存在於自然界，並以此解釋某些花的五邊形形態（與黄金分割率相關）。法國菊的「瓣」（舌狀花）數通常為斐氏數。1830年，K. F. Schimper和A. Braun發現植物的旋生葉序中，連續兩塊葉之間轉過的角度與周角之比，約成整數比時，常出現斐氏數，如或。

恆等式
資料來源：

證明以下的恆等式有很多方法。以下會用組合論述來證明。
 可以表示用多個1和多個2相加令其和等於的方法的數目。
不失一般性，我們假設，是計算了將1和2加到n的方法的數目。若第一個被加數是1，有種方法來完成對的計算；若第一個被加數是2，有來完成對的計算。因此，共有種方法來計算n的值。

計算用多個1和多個2相加令其和等於的方法的數目，同時至少一個加數是2的情況。

如前所述，當，有種這樣的方法。因為當中只有一種方法不用使用2，就即　（項），於是我們從減去1。

若第1個被加數是2，有種方法來計算加至的方法的數目；
若第2個被加數是2、第1個被加數是1，有種方法來計算加至的方法的數目。
重複以上動作。
若第個被加數為2，它之前的被加數均為1，就有種方法來計算加至0的數目。

若該數式包含2為被加數，2的首次出現位置必然在第1和的被加數之間。2在不同位置的情況都考慮到後，得出為要求的數目。



，其中與的序數皆不限於正整數。
特別地，當時，
更特別地，當或時，對於數列連續三項，有
另一方面，當時，對於數列連續四項，有
且，其中為黃金比例，為任意整數
藉由上述公式，又可推得以下恆等式：

特別地，當時，

 數論性質 
 公因數和整除關係 
整除，若且唯若整除，其中。

任意連續三個菲波那契數兩兩互質，亦即，對於每一個，

斐波那契质数

在斐波那契數列中，有質數：
2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……

截至2015年，已知最大的斐波那契質數是第104911個斐波那契數，一共有21925個十進制位。不过，人们仍不知道是不是有无限个斐波那契质数。

如所述，總能被整除，故除之外，任何斐氏質數的下標必同為質數。由於存在的一列連續合数，斐氏數列中亦能找到連續任意多項全為合數。

大於的斐氏數，必不等於質數加一或減一。

 與其他數列的交集 
斐波那契数列中，只有3個平方數：0、1、144。2001年，證明，斐氏數中的次方數衹有有限多個。2006年，Y. Bugeaud、M. Mignotte、S. Siksek三人證明，斐波那契数中的次方數只有0、1、8、144。

1、3、21、55為僅有的斐氏三角形數。曾猜想此結論，後來由罗明證明。

斐波那契數不能為完全数。推而廣之，除1之外，其他斐氏數皆非多重完全數，任兩個斐氏數之比亦不能是完全數。

 模n的週期性 

斐波那契數列各項模的餘數構成，其最小正週期稱為皮萨诺周期，至多為。皮薩諾週期對不同值的通項公式仍是未解問題，其中一步需要求出某個整數（同餘意義下）或二次有限域元素的。不過，對固定的，求解模的皮薩諾週期是問題的特例。

推廣
斐波那西數列是斐波那西n步數列步數為2的特殊情況，也和盧卡斯數列有關。
和盧卡斯數列的關係

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

如果它以1,-1開始，之後的數是：1,-1,2,-3,5,-8, ...

即是，

亦可寫成，其中是非負整數。

反費波那西數列兩項之間的比會趨近。
證明關係式
證明，其中是非負整數
以表示黃金分割數，則有
故，因此

巴都萬數列
費波那西數列可以用一個接一個的正方形來表現，巴都萬數列則是用一個接一個的等邊三角形來表現，它有的關係。

佩爾數列

佩爾數列的遞歸公式為，前幾項為0,1,2,5,12,29,70,169,408,...

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

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

 電腦科學 
考慮以輾轉相除法求兩個正整數的最大公因數，分析此算法的運行時間。同等輸入規模下，最壞情況（用時最長）發生於輸入為兩個相鄰斐氏數時。
归并排序算法有一多相（）版本用到斐氏數列，是將未排序的數組分為兩份，長度為相鄰的斐氏數（因此比值接近黃金比）。《计算机程序设计艺术》描述了此種的實作方法，適用於以磁带机為外存的情況。
斐波那契樹是一棵二叉树，其每個節點的左右子树高皆恰好差1。由此，斐氏樹為AVL树，且對固定高度而言，是最少節點的AVL樹。此類樹的節點數可寫成斐氏數減1。 Myron J. Ricci 的英文翻譯 載於 Soviet Mathematics - Doklady, 3:1259–1263, 1962.
 某些伪随机数生成器用到斐氏數列。
 斐波那契堆是一種數據結構，分析其時間複雜度時會用到斐波那契數。
斐波那契编码是以01字串表示正整數的一種方法，與之類似，還可以表示負數。

 延伸閱讀 
 KNUTH, D. E. 1997. The Art of Computer ProgrammingArt of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley. Chapter 1.2.8.
 Arakelian, Hrant (2014). Mathematics and History of the Golden Section. Logos, 404 p. ISBN 978-5-98704-663-0, (rus.)
 克裏福德A皮科夫.數學之戀.湖南科技出版社.

 參考文獻 



 註釋 

參見
齊肯多夫定理

外部連結
費波那契數，孫智宏（pdf）
 Periods of Fibonacci Sequences Mod m at MathPages
 Scientists find clues to the formation of Fibonacci spirals in nature 



Fibonacci