定義
斐波那契數列指的是這樣一個數列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........
自然中的斐波那契數列這個數列從第3項開始，每一項都等於前兩項之和。
斐波那契數列的定義者，是義大利數學家列昂納多·斐波那契（Leonardo Fibonacci），生於公元1170年，卒於1250年，籍貫是比薩。他被人稱作“比薩的列昂納多”。1202年，他撰寫了《算盤全書》（Liber Abacci）一書。他是第一個研究了印度和阿拉伯數學理論的歐洲人。他的父親被比薩的一家商業團體聘任為外交領事，派駐地點於阿爾及利亞地區，列昂納多因此得以在一個阿拉伯老師的指導下研究數學。他還曾在埃及、敘利亞、希臘、西西里和普羅旺斯等地研究數學。
通項公式
遞推公式
斐波那契數列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
如果設F(n）為該數列的第n項（n∈N*），那么這句話可以寫成如下形式：:F(n)=F(n-1)+F(n-2)
顯然這是一個線性遞推數列。
通項公式
斐波那契數列(如上，又稱為“比內公式”，是用無理數表示有理數的一個範例。)
斐波那契數列
斐波那契數列註：此時
通項公式推導
方法一：利用特徵方程（線性代數解法）
斐波那契數列
斐波那契數列
斐波那契數列
斐波那契數列
斐波那契數列
斐波那契數列
斐波那契數列線性遞推數列的特徵方程為：
x²=x+1
解得
則
∵
∴
解得
方法二：待定係數法構造等比數列1（初等代數解法）
設常數r，s .
斐波那契數列使得
則r+s=1，－rs=1
n≥3時，有
斐波那契數列
斐波那契數列
斐波那契數列……
斐波那契數列聯立以上n-2個式子，得：
斐波那契數列
斐波那契數列 斐波那契數列∵ ，
上式可化簡得：
斐波那契數列那么
斐波那契數列
斐波那契數列……
斐波那契數列
斐波那契數列
斐波那契數列
斐波那契數列
斐波那契數列（這是一個以 為首項、以 為末項、 為公比的等比數列的各項的和）。
斐波那契數列
斐波那契數列
斐波那契數列
斐波那契數列
斐波那契數列， 的解為
斐波那契數列則
方法三：待定係數法構造等比數列2（初等代數解法）
斐波那契數列設
斐波那契數列得
斐波那契數列構造方程
斐波那契數列解得 ，所以
斐波那契數列
斐波那契數列由(1)(2)式得
斐波那契數列
斐波那契數列
斐波那契數列化簡可得
斐波那契數列方法四：母函式法。
對於斐波那契數列{a}，有a=a=1,a=a+a(n>2時)
令S(x)=ax+ax+…+ax +...
那么有S(x)*(1-x-x)=ax+(a-a)x+…+(a-a-a)x +...=x
斐波那契數列因此S(x)= .
斐波那契數列
斐波那契數列 斐波那契數列 斐波那契數列不難證明1-x-x=-(x+ )(x+ )=(1- *x)(1- *x).
斐波那契數列 斐波那契數列 斐波那契數列因此S(x)= *[x/(1- *x)-x/(1- *x)].
再利用展開式1/(1-x)=1+x+x+x+…+x +…
於是就可以得S(x)=bx+bx+…+bx +…
斐波那契數列 斐波那契數列 斐波那契數列其中b= *[( ) - ( ) ].
斐波那契數列 斐波那契數列 斐波那契數列
斐波那契數列因此可以得到a=b= *[( )- ( )]
與黃金分割
關係
有趣的是，這樣一個完全是自然數的數列，通項公式卻是用無理數來表達的。而且當n趨向於無窮大時，前一項與後一項的比值越來越逼近黃金分割0.618（或者說後一項與前一項的比值小數部分越來越逼近0.618）。
1÷1=1，1÷2=0.5，2÷3=0.666...，3÷5=0.6，5÷8=0.625…………，55÷89=0.617977……………144÷233=0.618025…46368÷75025=0.6180339886…...
越到後面，這些比值越接近黃金比.
證明
斐波那契數列
斐波那契數列兩邊同時除以 得到：
斐波那契數列。
斐波那契數列若 的極限存在，設其極限為x，
斐波那契數列則 。
斐波那契數列所以 。
斐波那契數列由於
斐波那契數列解得
所以極限是黃金分割比。
特性
平方與前後項
從第二項開始，每個偶數項的平方都比前後兩項之積少1，每個奇數項的平方都比前後兩項之積多1。
如：第二項1的平方比它的前一項1和它的後一項2的積2少1，第三項2的平方比它的前一項1和它的後一項3的積3多1。
（註： 奇數項和偶數項是 指項數的奇偶，而並不是指數列的數字本身的奇偶，比如從數列第二項1開始數，第4項5是奇數，但它是偶數項，如果認為5是奇數項，那就誤解題意，怎么都說不通）
證明經計算可得：[f(n)]^2-f(n-1)f(n+1)=(-1)^(n-1)
與集合子集
斐波那契數列的第n+2項同時也代表了集合{1,2,...,n}中所有不包含相鄰正整數的子集個數。
奇數項求和
斐波那契數列偶數項求和
斐波那契數列平方求和
斐波那契數列隔項關係
f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1，且n≥1]
兩倍項關係
f(2n)/f(n)=f(n-1)+f(n+1)
其他公式
斐波那契數列套用
生活斐波那契
合併圖冊斐波那契數列中的斐波那契數會經常出現在我們的眼前——比如松果、鳳梨、樹葉的排列、某些花朵的花瓣數（典型的有向日葵花瓣），蜂巢，蜻蜓翅膀，超越數e（可以推出更多），黃金矩形、黃金分割、等角螺線，十二平均律等。
斐波那契數與植物花瓣3………………………
百合和蝴蝶花5……………………
藍花耬斗菜、金鳳花、飛燕草、毛茛花8………………………
翠雀花13………………………
金盞和玫瑰21……………………
紫宛34、55、89……………雛菊
斐波那契數還可以在植物的葉、枝、莖等排列中發現。例如，在樹木的枝幹上選一片葉子，記其為數0，然後依序點數葉子（假定沒有折損），直到到達與那些葉子正對的位置，則其間的葉子數多半是斐波那契數。葉子從一個位置到達下一個正對的位置稱為一個循回。葉子在一個循回中旋轉的圈數也是斐波那契數。在一個循回中葉子數與葉子旋轉圈數的比稱為葉序（源自希臘詞，意即葉子的排列）比。多數的葉序比呈現為斐波那契數的比。
黃金分割
隨著數列項數的增加，前一項與後一項之比越來越逼近黃金分割的數值0.6180339887..…
楊輝三角
將楊輝三角左對齊，成如圖所示排列，將同一斜行的數加起來，即得一數列1、1、2、3、5、8、……
斐波那契數列公式表示如下：
f⑴=C(0,0)=1。
f⑵=C(1,0)=1。
f⑶=C(2,0)+C(1,1)=1+1=2。
f⑷=C(3,0)+C(2,1)=1+2=3。
f⑸=C(4,0)+C(3,1)+C(2,2)=1+3+1=5。
f⑹=C(5,0)+C(4,1)+C(3,2)=1+4+3=8。
f⑺=C(6,0)+C(5,1)+C(4,2)+C(3,3)=1+5+6+1=13。
……
f(n)=C(n-1,0)+C(n-2,1)+…+C(n-1-m,m) (m<=n-1-m)
矩形面積
斐波那契數列與矩形面積的生成相關，由此可以導出一個斐波那契數列的一個性質。
斐波那契數列斐波那契數列前幾項的平方和可以看做不同大小的正方形，由於斐波那契的遞推公式，它們可以拼成一個大的矩形。這樣所有小正方形的面積之和等於大矩形的面積。則可以得到如下的恆等式：
質數數量
斐波那契數列的整除性與質數生成性
每3個連續的數中有且只有一個被2整除，
斐波那契數列每4個連續的數中有且只有一個被3整除，
每5個連續的數中有且只有一個被5整除，
每6個連續的數中有且只有一個被8整除，
每7個連續的數中有且只有一個被13整除，
每8個連續的數中有且只有一個被21整除，
每9個連續的數中有且只有一個被34整除，
.......
我們看到第5、7、11、13、17、23位分別是質數：5，13，89，233，1597，28657（第19位不是）
斐波那契數列的質數無限多嗎？
尾數循環
斐波那契數列的個位數：一個60步的循環
11235,83145,94370,77415,61785.38190,
99875,27965,16730,33695,49325,72910…
進一步，斐波那契數列的最後兩位數是一個300步的循環，最後三位數是一個1500步的循環，最後四位數是一個15000步的循環，最後五位數是一個150000步的循環。
自然界中“巧合”
斐波那契數列在自然科學的其他分支，有許多套用。例如，樹木的生長，由於新生的枝條，往往需要一段“休息”時間，供自身生長，而後才能萌發新枝。所以，一株樹苗在一段間隔，例如一年，以後長出一條新枝；第二年新枝“休息”，老枝依舊萌發；此後，老枝與“休息”過一年的枝同時萌發，當年生的新枝則次年“休息”。這樣，一株樹木各個年份的枝椏數，便構成斐波那契數列。這個規律，就是生物學上著名的“魯德維格定律”。
另外，觀察延齡草、野玫瑰、南美血根草、大波斯菊、金鳳花、耬斗菜、百合花、蝴蝶花的花瓣，可以發現它們花瓣數目具有斐波那契數：3、5、8、13、21、……
斐波那契數列其中百合花花瓣數目為3，梅花5瓣，飛燕草8瓣，萬壽菊13瓣，向日葵21或34瓣，雛菊有34,55和89三個數目的花瓣。
斐波那契螺旋：具有13條順時針旋轉和21條逆時針旋轉的螺旋的薊的頭部
這些植物懂得斐波那契數列嗎？應該並非如此，它們只是按照自然的規律才進化成這樣。這似乎是植物排列種子的“最佳化方式”，它能使所有種子具有差不多的大小卻又疏密得當，不至於在圓心處擠了太多的種子而在圓周處卻又稀稀拉拉。葉子的生長方式也是如此，對於許多植物來說，每片葉子從中軸附近生長出來，為了在生長的過程中一直都能最佳地利用空間（要考慮到葉子是一片一片逐漸地生長出來，而不是一下子同時出現的），每片葉子和前一片葉子之間的角度應該是222.5度，這個角度稱為“黃金角度”，因為它和整個圓周360度之比是黃金分割數0.618033989……的倒數，而這種生長方式就決定了斐波那契螺旋的產生。向日葵的種子排列形成的斐波那契螺旋有時能達到89，甚至144條。1992年，兩位法國科學家通過對花瓣形成過程的計算機仿真實驗，證實了在系統保持最低能量的狀態下，花朵會以斐波那契數列長出花瓣。
數字謎題
三角形的三邊關係定理和斐波那契數列的一個聯繫：
現有長為144cm的鐵絲，要截成n小段（n>2），每段的長度不小於1cm，如果其中任意三小段都不能拼成三角形，則n的最大值為多少？
分析：由於形成三角形的充要條件是任何兩邊之和大於第三邊，因此不構成三角形的條件就是存在兩邊之和不超過另一邊。截成的鐵絲最小為1，因此可以放2個1，第三條線段就是2（為了使得n最大，因此要使剩下來的鐵絲儘可能長，因此每一條線段總是前面的相鄰2段之和），依次為：1、1、2、3、5、8、13、21、34、55，以上各數之和為143，與144相差1，因此可以取最後一段為56，這時n達到最大為10。
我們看到，“每段的長度不小於1”這個條件起了控制全局的作用，正是這個最小數1產生了斐波那契數列，如果把1換成其他數，遞推關係保留了，但這個數列消失了。這裡，三角形的三邊關係定理和斐波那契數列發生了一個聯繫。
在這個問題中，144>143，這個143是斐波那契數列的前n項和，我們是把144超出143的部分加到最後的一個數上去，如果加到其他數上，就有3條線段可以構成三角形了。
影視作品中的斐波那契數列
斐波那契數列在歐美可謂是盡人皆知，於是在電影這種通俗藝術中也時常出現，比如在風靡一時的《達文西密碼》里它就作為一個重要的符號和情節線索出現，在《魔法玩具城》里又是在店主招聘會計時隨口問的問題。可見此數列就像黃金分割一樣流行。可是雖說叫得上名，多數人也就背過前幾個數，並沒有深入理解研究。在電視劇中也出現斐波那契數列，比如：日劇《考試之神》第五回，義嗣做全國模擬考試題中的最後一道數學題~在FOX熱播美劇《Fringe》中更是無數次引用，甚至作為全劇宣傳海報的設計元素之一。
推廣
斐波那契—盧卡斯數列
盧卡斯數列1、3、4、7、11、18…，也具有斐波那契數列同樣的性質。（我們可稱之為斐波那契—盧卡斯遞推：從第三項開始，每一項都等於前兩項之和f(n) = f(n-1)+ f(n-2)。
盧卡斯數列的通項公式為 f(n)=[(1+√5)/2]^n+[(1-√5)/2]^n
這兩個數列還有一種特殊的聯繫（如下表所示），F(n)*L(n)=F(2n)，及L(n)=F(n-1)+F(n+1)
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … |
| 斐波那契數列F(n) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | … |
| 盧卡斯數列L(n) | 1 | 3 | 4 | 7 | 11 | 18 | 29 | 47 | 76 | 123 | … |
| F(n)*L(n) | 1 | 3 | 8 | 21 | 55 | 144 | 377 | 987 | 2584 | 6765 | … |
類似的數列還有無限多個，我們稱之為斐波那契—盧卡斯數列。
如1，4，5，9，14，23…，因為1，4開頭，可記作F[1，4]，斐波那契數列就是F[1，1]，盧卡斯數列就是F[1，3]，斐波那契—盧卡斯數列就是F[a，b]。
斐波那契—盧卡斯數列之間的廣泛聯繫
①任意兩個或兩個以上斐波那契—盧卡斯數列之和或差仍然是斐波那契—盧卡斯數列。
如：F[1,4]n+F[1,3]n=F[2,7]n，F[1,4]n-F[1,3]n=F[0,1]n=F[1,1](n-1），
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … |
| F[1,4]n | 1 | 4 | 5 | 9 | 14 | 23 | 37 | 60 | 97 | 157 | … |
| F[1,3]n | 1 | 3 | 4 | 7 | 11 | 18 | 29 | 47 | 76 | 123 | … |
| F[1,4]n-F[1,3]n | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | … |
| F[1,4]n+F[1,3]n | 2 | 7 | 9 | 16 | 25 | 41 | 66 | 107 | 173 | 280 | … |
②任何一個斐波那契—盧卡斯數列都可以由斐波那契數列的有限項之和獲得，如
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … |
| F[1,1](n) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | … |
| F[1,1](n-1) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | … |
| F[1,1](n-1) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | … |
| F[1,3]n | 1 | 3 | 4 | 7 | 11 | 18 | 29 | 47 | 76 | 123 | … |
黃金特徵與孿生斐波那契—盧卡斯數列
斐波那契—盧卡斯數列的另一個共同性質：中間項的平方數與前後兩項之積的差的絕對值是一個恆值，
斐波那契數列：|1*1-1*2|=|2*2-1*3|=|3*3-2*5|=|5*5-3*8|=|8*8-5*13|=…=1
盧卡斯數列：|3*3-1*4|=|4*4-3*7|=…=5
F[1，4]數列：|4*4-1*5|=11
F[2，5]數列：|5*5-2*7|=11
F[2，7]數列：|7*7-2*9|=31
斐波那契數列這個值是1最小，也就是前後項之比接近黃金比例最快，我們稱為黃金特徵，黃金特徵1的數列只有斐波那契數列，是獨生數列。盧卡斯數列的黃金特徵是5，也是獨生數列。前兩項互質的獨生數列只有斐波那契數列和盧卡斯數列這兩個數列。
而F[1，4]與F[2，5]的黃金特徵都是11，是孿生數列。F[2，7]也有孿生數列：F[3，8]。其他前兩項互質的斐波那契—盧卡斯數列都是孿生數列，稱為孿生斐波那契—盧卡斯數列。
廣義斐波那契數列
斐波那契數列的黃金特徵1，還讓我們聯想到佩爾數列：1，2，5，12，29，…，也有|2*2-1*5|=|5*5-2*12|=…=1（該類數列的這種特徵值稱為勾股特徵）。
佩爾數列Pn的遞推規則：P1=1，P2=2，Pn=P(n-2)+2P(n-1).
據此類推到所有根據前兩項導出第三項的通用規則：f(n) = f(n-1) * p + f(n-2) * q，稱為廣義斐波那契數列。
當p=1，q=1時，我們得到斐波那契—盧卡斯數列。
當p=1，q=2時，我們得到佩爾—勾股弦數（跟邊長為整數的直角三角形有關的數列集合）。
當p=2，q=-1時，我們得到等差數列。其中f1=1，f2=2時，我們得到自然數列1，2，3，4…。自然數列的特徵就是每個數的平方與前後兩數之積的差為1（等差數列的這種差值稱為自然特徵）。
具有類似黃金特徵、勾股特徵、自然特徵的廣義——斐波那契數列p=±1。
當f1=1，f2=2，p=2，q=0 時，我們得到等比數列1，2，4，8，16……
相關數學
排列組合
有一段樓梯有10級台階，規定每一步只能跨一級或兩級，要登上第10級台階有幾種不同的走法?
這就是一個斐波那契數列：登上第一級台階有一種登法；登上兩級台階，有兩種登法；登上三級台階，有三種登法；登上四級台階，有五種登法……
1，2，3，5，8，13……所以，登上十級，有89種走法。
類似的，一枚均勻的硬幣擲10次，問不連續出現正面的可能情形有多少種？
答案是（1/√5)*{[(1+√5)/2]^(10+2) - [(1-√5)/2]^(10+2)}=144種。
求遞推數列a⑴=1，a(n+1)=1+1/a(n）的通項公式
由數學歸納法可以得到：a(n)=F(n+1)/F(n），將斐波那契數列的通項式代入，化簡就得結果。
兔子繁殖問題
斐波那契數列又因數學家列昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數列”。
一般而言，兔子在出生兩個月後，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔子都不死，那么一年以後可以繁殖多少對兔子？
我們不妨拿新出生的一對小兔子分析一下：
第一個月小兔子沒有繁殖能力，所以還是一對
兩個月後，生下一對小兔對數共有兩對
三個月以後，老兔子又生下一對，因為小兔子還沒有繁殖能力，所以一共是三對
－－－－－－
依次類推可以列出下表：
| 經過月數 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | … |
| 幼仔對數 | 1 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | … |
| 成兔對數 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | |
| 總體對數 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 |
幼仔對數=前月成兔對數
成兔對數=前月成兔對數+前月幼仔對數
總體對數=本月成兔對數+本月幼仔對數
可以看出幼仔對數、成兔對數、總體對數都構成了一個數列。這個數列有關十分明顯的特點，那是：前面相鄰兩項之和，構成了後一項。
這個數列是義大利中世紀數學家斐波那契在<算盤全書>中提出的，這個級數的通項公式，除了具有a(n+2)=an+a(n+1)的性質外，還可以證明通項公式為：an=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}（n=1,2,3,...）
數列與矩陣
對於斐波那契數列1、1、2、3、5、8、13、……。有如下定義
F(n)=F(n-1)+F(n-2)
F(1)=1
F(2)=1
對於以下矩陣乘法
F(n+1) = (1,1 ) (F(n),F(n-1))
F(n) =(1,0 ) (F(n),F(n-1))
它的運算就是右邊的矩陣 (1,1)乘以矩陣(F(n),F(n-1))，右邊的矩陣(1,0 ) 乘以矩陣(F(n),F(n-1))，得到：
F(n+1)=F(n)+F(n-1)
F(n)=F(n)
可見該矩陣的乘法完全符合斐波那契數列的定義
設矩陣A=第一行（1，1）第二行（1，0） 疊代n次可以得到：F(n+1) =A^(n) *（ F(2)，F(1)) = A^(n)*(1,1)
這就是斐波那契數列的矩陣乘法定義。
另矩陣乘法的一個運算法則A^n(n為偶數) = A^(n/2)* A^(n/2)，這樣我們通過二分的思想，可以實現對數複雜度的矩陣相乘。
因此可以用遞歸的方法求得答案。
數列值的另一種求法：
F(n) = [ (( sqrt ( 5 ) + 1 ) / 2) ^ n ]
其中[ x ]表示取距離 x 最近的整數。
斐波那契弧線
斐波那契數列斐波那契弧線，也稱為斐波那契扇形線。第一，此趨勢線以二個端點為準而畫出，例如，最低點反向到最高點線上的兩個點。然後通過第二點畫出一條“無形的（看不見的）”垂直線。然後，從第一個點畫出第三條趨勢線：38.2%， 50%和61.8%的無形垂直線交叉。
斐波納契弧線，是潛在的支持點和阻力點水平價格。斐波納契弧線和斐波納契扇形線常常在圖表里同時繪畫出。支持點和阻力點就是由這些線的交匯點得出。
要注意的是弧線的交叉點和價格曲線會根據圖表數值範圍而改變，因為弧線是圓周的一部分，它的形成總是一樣的。
C++代碼實現
基本循環算法
遞歸算法實現
遞歸算法最佳化(記憶化搜尋)
高精度計算
