斐波那契数
-{zh-hant:費波那契數;zh-hans:斐波那契数}-（意大利语：Successione di Fibonacci），又譯為菲波拿契數、菲波那西數、斐氏數、黃金分割數。所形成的數列稱為-{zh-hant:費波那契數列;zh-hans:斐波那契数列}-（意大利语：Successione di Fibonacci），又譯為菲波拿契數列、菲波那西數列、斐氏數列、黃金分割數列。 在數學上，斐波那契數是以遞歸的方法來定義：用文字來說，就是斐波那契數列由0和1開始，之後的斐波那契數就是由之前的兩數相加而得出。首幾個斐波那契數是：
特別指出：0不是第一項，而是第零項。 公元1150年印度數學家Gopala和金月在研究箱子包裝物件長宽剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是比薩的李奧納多（義大利人斐波那契Leonardo Fibonacci），他描述兔子生長的數目時用上了這數列:
假設在n月有兔子總共a對，n+1月總共有b對。在n+2月必定總共有a+b對：因為在n+2月的時候，前一月（n+1月）的b對兔子可以存留至第n+2月（在當月屬於新誕生的兔子尚不能生育）。而新生育出的兔子對數等於所有在n月就已存在的a對
斐波纳契数也是帕斯卡三角形的每一条红色对角线上数字的和。
為求得斐波那契數列的一般表達式，可以藉助線性代數的方法。高中的初等數學知識也能求出。 已知
設formula_7化簡得formula_8 比較係數可得： formula_9 不妨設formula_10 解得：
formula_11
又因为有formula_7， 即formula_13為等比數列。
由以上可得： formula_15
變形得： formula_16。 令formula_17
formula_20 設formula_21，解得formula_22。 故數列formula_23為等比數列 即formula_24。而formula_25， 故有formula_26 又有formula_11 和formula_17 可得formula_29
得出formula_30表達式
formula_29
formula_32
formula_33
設J為第n個月有生育能力的兔子數量，A為這一月份的兔子數量。
上式表達了兩個月之間，兔子數目之間的關係。而要求的是，A的表達式。
根据特征值的计算公式，我们需要算出来 formula_36 所对应的解。
展开行列式有：formula_37。
故當行列式的值為 0，解得 formula_38 或 formula_39。
將兩個特徵值代入
求特徵向量formula_41得
formula_42=formula_43
formula_44=formula_45
第一個月的情況是兔子一對，新生0對。
將它分解為用特徵向量表示。
從
可得到
將（4） 代入 （5）
根據3
現在在6的基礎上，可以很快求出A的表達式，將兩個特徵值代入6中
（7）即為A的表達式
實際上，如果將斐波那契數列的通項公式寫成formula_56，即可利用解二階線性齊次遞迴關係式的方法，寫出其特徵多項式formula_57（該式和表達斐波那契數列的矩陣的特徵多項式一致），然後解出formula_58=formula_59，formula_60=formula_61，即有formula_62，其中formula_63为常数。我们知道formula_64，因此formula_65，解得formula_66。
formula_67
設formula_69為黃金比例formula_70，則有恆等式formula_71與formula_72，其中formula_73為任意整數，則
formula_74
因此得到formula_75的一般式：
formula_76
此一般式對任意整數formula_73成立
當formula_73為足夠大的正整數時
可通過編程觀察斐波那契數列。分為兩類問題，一種已知數列中的某一項，求序數。第二種是已知序數，求該項的值。
可通過遞歸遞推的算法解決此兩個問題。 事實上當n相當巨大的時候，O（n）的遞推/遞歸非常慢……這時候要用到矩陣快速幂這一技巧，可以使遞迴加速到O(logn)。
開普勒發現數列前、後兩項之比1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ... ,也組成了一個數列，會趨近黃金分割：
斐波那契數亦可以用連分數來表示：
formula_82
formula_83
而黃金分割數亦可以用無限連分數表示： 而黃金分割數也可以用無限多重根號表示：
斐波那契数列中，只有3個平方數：0、1、144。 證明以下的恆等式有很多方法。以下會用組合論述來證明。 不失一般性，我們假設formula_89，formula_90是計算了將1和2加到n的方法的數目。若第一個被加數是1，有formula_75種方法來完成對formula_92的計算；若第一個被加數是2，有formula_93來完成對formula_94的計算。因此，共有formula_95種方法來計算n的值。 計算用多個1和多個2相加令其和等於formula_97的方法的數目，同時至少一個加數是2的情況。
如前所述，當formula_98，有formula_99種這樣的方法。因為當中只有一種方法不用使用2，就即formula_100　（formula_97項），於是我們從formula_99減去1。若該數式包含2為被加數，2的首次出現位置必然在第1和formula_97的被加數之間。2在不同位置的情況都考慮到後，得出formula_110為要求的數目。 特別地，當"m" = "n"時，
斐波那西數列是斐波那西n步數列步數為2的特殊情況，也和盧卡斯數列有關。 反費波那西數列的遞歸公式如下：
如果它以1,-1開始，之後的數是：1,-1,2,-3,5,-8, ...
即是formula_128。
反費波那西數列兩項之間的比會趨近formula_129。
費波那西數列可以用一個接一個的正方形來表現，巴都萬數列則是用一個接一個的等邊三角形來表現，它有formula_130的關係。
佩爾數列的遞歸公式為formula_131，前幾項為0,1,2,5,12,29,70,169,408...
1970年，尤裏·馬季亞謝維奇指出了偶角標的斐波那契函數 正是滿足Julia Robison假設的丟番圖函數，因而證明了希爾伯特第十問題是不可解的。
在斐波那契數列中，有質數： 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……
目前已知最大質數是第81839個斐波那契數，一共有17103位數。不过，人们仍不知道是不是无限个有斐波那契质数。
JavaScript迭代版
function fib(n) { alert(fib(40)); C语言通项公式版int main() c++二變數求某項版 using namespace std; int main () {
c++通项公式版 using namespace std; int main() Python语言通项公式版
def fib(n): # write Fibonacci series up to n
def fib2(n): # return Fibonacci series up to n fibs = [0, 1] numZS = int(input('How many Fibonacci numbers do you want? ')) for i in range(numZS-2): print fibs Common Lisp
Go
遞迴版，時間複雜度為 O(2^n)：
func fibonacci(n int) int {
通用版，時間複雜度為 O(n)：
func fibonacci(n int) int {
Java语言通项公式版：
public int fibonacci(int n){ Java语言快捷版：
public int fibonacci(int n){
C语言陣列版：
int main()
Python Lambda 遞迴版:
fib = lambda n: n if n<2 else fib(n-1) + fib(n-2)