今天要講解的數學知識與程式員面試密不可分，很多程式員面試都會被問到該知識。
一、定義
斐波那契數列（Fibonacci sequence）又稱黃金分割數列，以兔子繁殖為例子而引入，故又稱為“兔子數列”。指的是這樣一個數列：0、1、1、2、3、5、8、13、21、34、……，這個數列從第 3 項開始，每一項都等于前兩項之和。
在數學上，斐波那契數列以如下被以遞推的方法定義：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。
斐波那契數列的定義者，是意大利數學家萊昂納多·斐波那契（Leonardo Fibonacci）。生于公元 1170 年，卒于 1250 年，籍貫是比薩。他被人稱作“比薩的萊昂納多”。1202 年，他撰寫了《算盤全書》（Liber Abacci）一書。他是第一個研究了印度和阿拉伯數學理論的歐洲人。他的父親被比薩的一家商業團體聘任為外交領事，派駐地點于阿爾及利亞地區，萊昂納多是以得以在一個阿拉伯老師的指導下研究數學。他還曾在埃及、叙利亞、希臘、西西裡和普羅旺斯等地研究數學，另外斐波納契還在計算機C語言程式題中應用廣泛。
萊昂納多·斐波那契
二、通項公式
遞推公式
如果設 an 為該數列的第 n 項（
），那麼這句話可以寫成如下形式：
顯然這是一個線性遞推數列。
通項公式
⑴
(如上，又稱為“比内公式”，是用無理數表示有理數的一個範例。)
注：此時
⑵ an=[(2/√5+1)-1/(√5+1/2)ⁿ]/√5
通項公式推導
方法一：利用特征方程（線性代數解法）
線性遞推數列的特征方程為：
解得
則
解得
方法二：待定系數法構造等比數列1（初等代數解法）
設常數
，
使得
則
時，有：
聯立以上
個式子，得：
上式可化簡得：
那麼：
（這是一個以
為首項、以
為末項、
為公比的等比數列的各項的和）。
， 的解為
，
則
方法三：待定系數法構造等比數列（初等代數解法）
得
構造方程
解得
是以：
由(1)、(2)式得：
令：
化簡可得：
方法四：母函數法。
對于斐波那契數列
，有
（
）
令
那麼有：
是以
.
不難證明：
是以
再利用展開式
于是就可以得
其中
是以可以得到：
與黃金分割的關系
有趣的是，這樣一個完全是自然數的數列，通項公式卻是用無理數來表達的。而且當
趨向于無窮大時，前一項與後一項的比值越來越逼近黃金分割0.618（或者說後一項與前一項的比值小數部分越來越逼近 0.618）。
越到後面，
的比值越接近黃金比。
三、應用
生活斐波那契
斐波那契數列中的斐波那契數會經常出現在我們的眼前——比如松果、鳳梨、樹葉的排列、某些花朵的花瓣數（典型的有向日葵花瓣），蜂巢，蜻蜓翅膀，超越數e（可以推出更多），黃金矩形、黃金分割、等角螺線等。
斐波那契數還可以在植物的葉、枝、莖等排列中發現。例如，在樹木的枝幹上選一片葉子，記其為數 0，然後依序點數葉子（假定沒有折損），直到到達與那些葉子正對的位置，則其間的葉子數多半是斐波那契數。葉子從一個位置到達下一個正對的位置稱為一個循回。葉子在一個循回中旋轉的圈數也是斐波那契數。在一個循回中葉子數與葉子旋轉圈數的比稱為葉序（源自希臘詞，意即葉子的排列）比。多數的葉序比呈現為斐波那契數的比。
黃金分割
随着數列項數的增加，前一項與後一項之比越來越逼近黃金分割的數值 0.6180339887..…
楊輝三角
将楊輝三角左對齊，成如圖所示排列，将同一斜行的數加起來，即得一數列 1、1、2、3、5、8、……
公式表示如下：
矩形面積
斐波那契數列與矩形面積的生成相關，由此可以導出一個斐波那契數列的一個性質。
斐波那契數列前幾項的平方和可以看做不同大小的正方形，由于斐波那契的遞推公式，它們可以拼成一個大的矩形。這樣所有小正方形的面積之和等于大矩形的面積。則可以得到如下的恒等式：
質數數量
斐波那契數列的整除性與質數生成性
每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 年，兩位法國科學家通過對花瓣形成過程的計算機仿真實驗，證明了在系統保持最低能量的狀态下，花朵會以斐波那契數列長出花瓣。
數字謎題
三角形的三邊關系定理和斐波那契數列的一個聯系：
現有長為 144 cm 的鐵絲，要截成n小段（n>2），每段的長度不小于 1 cm，如果其中任意三小段都不能拼成三角形，則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是斐波那契數列的前
項和，我們是把144超出143的部分加到最後的一個數上去，如果加到其他數上，就有3條線段可以構成三角形了。
影視作品中的斐波那契數列
斐波那契數列在歐美可謂是盡人皆知，于是在電影這種通俗藝術中也時常出現，比如在風靡一時的《達芬奇密碼》裡它就作為一個重要的符号和情節線索出現，在《魔法玩具城》裡又是在店主招聘會計時随口問的問題。可見此數列就像黃金分割一樣流行。可是雖說叫得上名，多數人也就背過前幾個數，并沒有深入了解研究。在電視劇中也出現斐波那契數列，比如：日劇《考試之神》第五回，義嗣做全國模拟考試題中的最後一道數學題~在FOX 熱播美劇《Fringe》中更是無數次引用，甚至作為全劇宣傳海報的設計元素之一。