斐波那契数

以斐波那契數為邊的正方形拼成的近似的黃金矩形(1:1.618)

斐波那契数（意大利语：Successione di Fibonacci），又譯為菲波拿契數、菲波那西數、斐氏數、黃金分割數。所形成的數列稱為斐波那契数列（意大利语：Successione di Fibonacci），又譯為菲波拿契數列、菲波那西數列、斐氏數列、黃金分割數列。

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

• $F_{0}=0$
• $F_{1}=1$
• $F_{n}=F_{n-1}+F_{n-2}$（n≧2）

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

1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89、 144、 233、 377、 610、 987……（OEIS數列A000045）

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

起源

公元1150年印度數學家Gopala和金月在研究箱子包裝物件長宽剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是比薩的李奧納多（義大利人斐波那契Leonardo Fibonacci, 1175－1250），他描述兔子生長的數目時用上了這數列:

兔子对的数量就是斐波那契数列

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

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

斐波纳契数是帕斯卡三角形的每一条红色对角线上数字的和。

斐波纳契数也是杨辉三角的每一条红色对角线上数字的和。

表達式

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

初等代數解法

已知

• $a_{1}=1$
• $a_{2}=1$
• $a_{n}=a_{n-1}+a_{n-2}$（n≥3）

首先構建等比數列

設$a_{n}+\alpha a_{n-1}=\beta (a_{n-1}+\alpha a_{n-2})$
化簡得
$a_{n}=(\beta -\alpha )a_{n-1}+\alpha \beta a_{n-2}$
比較係數可得：
${\begin{cases}\beta -\alpha =1\\\alpha \beta =1\end{cases}}$
不妨設$\beta >0,\alpha >0$
解得：

${\begin{cases}\alpha ={\dfrac {{\sqrt {5}}-1}{2}}\\\beta ={\dfrac {{\sqrt {5}}+1}{2}}\end{cases}}$
又因为有$a_{n}+\alpha a_{n-1}=\beta (a_{n-1}+\alpha a_{n-2})$， 即$\left\{a_{n}+\alpha a_{n-1}\right\}$為等比數列。

求出數列{$a_{n}+\alpha a_{n-1}$}

由以上可得：
${\begin{aligned}a_{n+1}+\alpha a_{n}&=(a_{2}+\alpha a_{1})\beta ^{n-1}\\&=(1+\alpha )\beta ^{n-1}\\&=\beta ^{n}\\\end{aligned}}$

變形得： ${\frac {a_{n+1}}{\beta ^{n+1}}}+{\frac {\alpha }{\beta }}\cdot {\frac {a_{n}}{\beta ^{n}}}={\frac {1}{\beta }}$。 令$b_{n}={\frac {a_{n}}{\beta ^{n}}}$

求數列{$b_{n}$}進而得到{$a_{n}$}

$b_{n+1}+{\frac {\alpha }{\beta }}b_{n}={\frac {1}{\beta }}$
設$b_{n+1}+\lambda =-{\frac {\alpha }{\beta }}(b_{n}+\lambda )$，解得$\lambda =-{\frac {1}{\alpha +\beta }}$。 故數列$\left\{b_{n}+\lambda \right\}$為等比數列
即$b_{n}+\lambda =\left(-{\frac {\alpha }{\beta }}\right)^{n-1}\left(b_{1}+\lambda \right)$。而$b_{1}={\frac {a_{1}}{\beta }}={\frac {1}{\beta }}$， 故有$b_{n}+\lambda =\left(-{\frac {\alpha }{\beta }}\right)^{n-1}\left({\frac {1}{\beta }}+\lambda \right)$
又有${\begin{cases}\alpha ={\dfrac {{\sqrt {5}}-1}{2}}\\\beta ={\dfrac {{\sqrt {5}}+1}{2}}\end{cases}}$ 和$b_{n}={\frac {a_{n}}{\beta ^{n}}}$
可得$a_{n}={\frac {\sqrt {5}}{5}}\cdot \left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right]$

得出${a_{n}}$表達式

$a_{n}={\frac {\sqrt {5}}{5}}\cdot \left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right]$

用數學歸納法證明表達式

證明$F_{n}={\frac {1}{\sqrt {5}}}[\varphi ^{n}-(1-\varphi )^{n}]$，其中$\varphi$為黃金比例${\frac {1+{\sqrt {5}}}{2}}$，$n$為任意整數

• 若$n$為非負整數

當$n=0$時，${\frac {1}{\sqrt {5}}}[\varphi ^{0}-(1-\varphi )^{0}]={\frac {1}{\sqrt {5}}}[1-1]=0=F_{0}$，成立

當$n=1$時，${\frac {1}{\sqrt {5}}}[\varphi ^{1}-(1-\varphi )^{1}]={\frac {1}{\sqrt {5}}}[\varphi -1+\varphi ]={\frac {1}{\sqrt {5}}}[2\varphi -1]={\frac {1}{\sqrt {5}}}\times {\sqrt {5}}=1=F_{1}$，成立

設當$n=k$及$n=k+1$時皆成立，即$F_{k}={\frac {1}{\sqrt {5}}}[\varphi ^{k}-(1-\varphi )^{k}]$且$F_{k+1}={\frac {1}{\sqrt {5}}}[\varphi ^{k+1}-(1-\varphi )^{k+1}]$

當$n=k+2$時

${\begin{aligned}F_{k+2}&=F_{k+1}+F_{k}\\&={\frac {1}{\sqrt {5}}}[\varphi ^{k+1}-(1-\varphi )^{k+1}]+{\frac {1}{\sqrt {5}}}[\varphi ^{k}-(1-\varphi )^{k}]\\&={\frac {1}{\sqrt {5}}}[\varphi ^{k+1}+\varphi ^{k}-(1-\varphi )^{k+1}-(1-\varphi )^{k}]\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{k}({\color {brown}\varphi +1})-(1-\varphi )^{k}[{\color {green}(1-\varphi )+1}]\right\}\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{k}({\color {brown}\varphi ^{2}})-(1-\varphi )^{k}[{\color {green}(1-\varphi )^{2}}]\right\}\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{k+2}-(1-\varphi )^{k+2}\right\}\\\end{aligned}}$

亦成立

• 若$n$為非正整數

當$n=0$時，成立

當$n=-1$時，${\frac {1}{\sqrt {5}}}[{\color {brown}\varphi ^{-1}}-{\color {green}(1-\varphi )^{-1}}]={\frac {1}{\sqrt {5}}}[({\color {brown}\varphi -1})-({\color {green}-\varphi })]={\frac {1}{\sqrt {5}}}[2\varphi -1]={\frac {1}{\sqrt {5}}}\times {\sqrt {5}}=1=F_{-1}$，成立

設當$n=-k$及$n=-k-1$時皆成立，即$F_{-k}={\frac {1}{\sqrt {5}}}[\varphi ^{-k}-(1-\varphi )^{-k}]$且$F_{-k-1}={\frac {1}{\sqrt {5}}}[\varphi ^{-k-1}-(1-\varphi )^{-k-1}]$

當$n=-k-2$時

${\begin{aligned}F_{-k-2}&=F_{-k}-F_{-k-1}\\&={\frac {1}{\sqrt {5}}}[\varphi ^{-k}-(1-\varphi )^{-k}]-{\frac {1}{\sqrt {5}}}[\varphi ^{-k-1}-(1-\varphi )^{-k-1}]\\&={\frac {1}{\sqrt {5}}}[\varphi ^{-k}-\varphi ^{-k-1}-(1-\varphi )^{-k}+(1-\varphi )^{-k-1}]\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{-k-1}({\color {brown}\varphi -1})-(1-\varphi )^{-k-1}[{\color {green}(1-\varphi )-1}]\right\}\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{-k-1}({\color {brown}\varphi ^{-1}})-(1-\varphi )^{-k-1}[{\color {green}(1-\varphi )^{-1}}]\right\}\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{-k-2}-(1-\varphi )^{-k-2}\right\}\\\end{aligned}}$

亦成立

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

線性代數解法

${\begin{pmatrix}F_{n+2}\\F_{n+1}\end{pmatrix}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}\cdot {\begin{pmatrix}F_{n+1}\\F_{n}\end{pmatrix}}$

${\begin{pmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_{n}\end{pmatrix}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n+1}$

構建一個矩陣方程

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

${J_{n+1} \choose A_{n+1}}={\begin{pmatrix}0&1\\1&1\end{pmatrix}}\cdot {J_{n} \choose A_{n}},$

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

求矩陣的特徵值：$\lambda$

根据特征值的计算公式，我们需要算出来 ${\begin{vmatrix}-\lambda &1\\1&1-\lambda \\\end{vmatrix}}=0$ 所对应的解。

展开行列式有：$-\lambda (1-\lambda )-1\times 1=\lambda ^{2}-\lambda -1$。

故當行列式的值為 0，解得 $\lambda _{1}={\frac {1}{2}}(1+{\sqrt {5}})$ 或 $\lambda _{2}={\frac {1}{2}}(1-{\sqrt {5}})$。

特徵向量

將兩個特徵值代入

$\left({\begin{pmatrix}0&1\\1&1\end{pmatrix}}-\lambda \cdot E\right)\cdot {\vec {x}}=0$

求特徵向量${\vec {x}}$得

${\vec {x}}_{1}$=${\begin{pmatrix}1\\{\frac {1}{2}}(1+{\sqrt {5}})\end{pmatrix}}$

${\vec {x}}_{2}$=${\begin{pmatrix}1\\{\frac {1}{2}}(1-{\sqrt {5}})\end{pmatrix}}$

分解首向量

第一個月的情況是兔子一對，新生0對。

${J_{1} \choose A_{1}}={\begin{pmatrix}0\\1\end{pmatrix}}$

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

${\begin{pmatrix}0\\1\end{pmatrix}}={\frac {1}{\sqrt {5}}}\cdot {\begin{pmatrix}1\\{\frac {1}{2}}(1+{\sqrt {5}})\end{pmatrix}}-{\frac {1}{\sqrt {5}}}\cdot {\begin{pmatrix}1\\{\frac {1}{2}}(1-{\sqrt {5}})\end{pmatrix}}$ （4）

用數學歸納法證明

從

${J_{n+1} \choose A_{n+1}}={\begin{pmatrix}0&1\\1&1\end{pmatrix}}\cdot {J_{n} \choose A_{n}}$=$\lambda \cdot {J_{n} \choose A_{n}}$

可得到

${J_{n+1} \choose A_{n+1}}={\begin{pmatrix}0&1\\1&1\end{pmatrix}}^{n}\cdot {J_{1} \choose A_{1}}=\lambda ^{n}\cdot {J_{1} \choose A_{1}}$ （5）

化簡矩陣方程

將（4） 代入 （5）

${J_{n+1} \choose A_{n+1}}=\lambda ^{n}\cdot \left[{\frac {1}{\sqrt {5}}}\cdot {\begin{pmatrix}1\\{\frac {1}{2}}(1+{\sqrt {5}})\end{pmatrix}}-{\frac {1}{\sqrt {5}}}\cdot {\begin{pmatrix}1\\{\frac {1}{2}}(1-{\sqrt {5}})\end{pmatrix}}\right]$

根據3

${J_{n+1} \choose A_{n+1}}={\frac {1}{\sqrt {5}}}\cdot \lambda _{1}^{n}\cdot {\begin{pmatrix}1\\{\frac {1}{2}}(1+{\sqrt {5}})\end{pmatrix}}-{\frac {1}{\sqrt {5}}}\cdot \lambda _{2}^{n}\cdot {\begin{pmatrix}1\\{\frac {1}{2}}(1-{\sqrt {5}})\end{pmatrix}}$

求A的表達式

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

$A_{n+1}={\frac {1}{\sqrt {5}}}\cdot \lambda _{1}^{n+1}-{\frac {1}{\sqrt {5}}}\cdot \lambda _{2}^{n+1}$

$A_{n+1}={\frac {1}{\sqrt {5}}}\cdot (\lambda _{1}^{n+1}-\lambda _{2}^{n+1})$

$A_{n+1}={\frac {1}{\sqrt {5}}}\cdot \left\{\left[{\frac {1}{2}}\left(1+{\sqrt {5}}\right)\right]^{n+1}-\left[{\frac {1}{2}}(1-{\sqrt {5}})\right]^{n+1}\right\}$（7）

（7）即為A_n+1的表達式

數論解法

實際上，如果將斐波那契數列的通項公式寫成$a_{n}-a_{n-1}-a_{n-2}=0$，即可利用解二階線性齊次遞迴關係式的方法，寫出其特徵多項式$\lambda ^{2}-\lambda -1=0$（該式和表達斐波那契數列的矩陣的特徵多項式一致），然後解出$\lambda _{1}$=${\frac {1}{2}}(1+{\sqrt {5}})$，$\lambda _{2}$=${\frac {1}{2}}(1-{\sqrt {5}})$，即有$a_{n}=c_{1}\lambda _{1}^{n}+c_{2}\lambda _{2}^{n}$，其中$c_{1},c_{2}$为常数。我们知道$a_{0}=0,a_{1}=1$，因此${\begin{cases}c_{1}+c_{2}=0\\{\frac {c_{1}(1+{\sqrt {5}})}{2}}+{\frac {c_{2}(1-{\sqrt {5}})}{2}}=1\end{cases}}$，解得$c_{1}={\frac {1}{\sqrt {5}}},c_{2}=-{\frac {1}{\sqrt {5}}}$。

組合數解法

$F_{n}=\sum _{i=0}^{\infty }{\binom {n-i}{i}}$

$F_{n-1}+F_{n}=\sum _{i=0}^{\infty }{\binom {n-1-i}{i}}+\sum _{i=0}^{\infty }{\binom {n-i}{i}}=1+\sum _{i=1}^{\infty }{\binom {n-i}{i-1}}+\sum _{i=1}^{\infty }{\binom {n-i}{i}}=1+\sum _{i=1}^{\infty }{\binom {n+1-i}{i}}=\sum _{i=0}^{\infty }{\binom {n+1-i}{i}}=F_{n+1}$

黃金比例恆等式解法

設$\varphi$為黃金比例${\frac {1+{\sqrt {5}}}{2}}$，則有恆等式$\varphi ^{n}=F_{n-1}+\varphi F_{n}$與$(1-\varphi )^{n}=F_{n+1}-\varphi F_{n}$，其中$n$為任意整數，則

${\begin{aligned}\varphi ^{n}-(1-\varphi )^{n}&=(F_{n-1}+\varphi F_{n})-(F_{n+1}-\varphi F_{n})\\&=(F_{n-1}-F_{n+1})+2\varphi F_{n}\\&=-F_{n}+2\varphi F_{n}\\&=F_{n}(2\varphi -1)\\&=F_{n}\times {\sqrt {5}}\\\end{aligned}}$

因此得到$F_{n}$的一般式：

${\begin{aligned}F_{n}&={\frac {1}{\sqrt {5}}}[\varphi ^{n}-(1-\varphi )^{n}]\\&={\frac {1}{\sqrt {5}}}\left[({\frac {1+{\sqrt {5}}}{2}})^{n}-({\frac {1-{\sqrt {5}}}{2}})^{n}\right]\\\end{aligned}}$

此一般式對任意整數$n$成立

近似值

當$n$為足夠大的正整數時

$F_{n}\approx {\frac {1}{\sqrt {5}}}\varphi ^{n}={\frac {1}{\sqrt {5}}}\cdot \left[{\frac {1}{2}}\left(1+{\sqrt {5}}\right)\right]^{n}\approx 0.4472135955\cdot 1.61803398875^{n}$

$F_{-n}\approx -{\frac {1}{\sqrt {5}}}(1-\varphi )^{-n}=-{\frac {1}{\sqrt {5}}}\cdot \left[{\frac {1}{2}}\left(1-{\sqrt {5}}\right)\right]^{-n}\approx -0.4472135955\cdot (-0.61803398875)^{-n}$

用計算機求解

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

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

和黃金分割的關係

開普勒發現數列前、後兩項之比1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ,...... ,也組成了一個數列，會趨近黃金分割：

${\frac {f_{n+1}}{f_{n}}}\approx a={\frac {1}{2}}(1+{\sqrt {5}})=\varphi \approx 1{.}618{...}$

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

${\frac {1}{1}}=1\qquad {\frac {2}{1}}=1+{\frac {1}{1}}\qquad {\frac {3}{2}}=1+{\frac {1}{1+{\frac {1}{1}}}}\qquad {\frac {5}{3}}=1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1}}}}}}\qquad {\frac {8}{5}}=1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1}}}}}}}}$

$F_{n}={\frac {1}{\sqrt {5}}}\left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right]={\varphi ^{n} \over {\sqrt {5}}}-{(1-\varphi )^{n} \over {\sqrt {5}}}$

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

$\varphi =1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1+...}}}}}}}}$

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

$\varphi ={\sqrt {1+{\sqrt {1+{\sqrt {1+{\sqrt {1+...}}}}}}}}$

和自然的關係

更多信息：自然界的圖案

参见：Golden ratio#Nature

春黄菊的頭狀花序上，小花呈螺旋狀排列，從不同方向可以數出21（深藍）和13（淺藍）條旋臂，為相鄰的斐氏數。類似的螺旋狀排列見於多種植物。

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

恆等式

資料來源：

證明以下的恆等式有很多方法。以下會用組合論述來證明。

• $F_{n}$可以表示用多個1和多個2相加令其和等於$n$的方法的數目。

不失一般性，我們假設$n\geq 1$，$F_{n+1}$是計算了將1和2加到n的方法的數目。若第一個被加數是1，有$F_{n}$種方法來完成對$n-1$的計算；若第一個被加數是2，有$F_{n-1}$來完成對$n-2$的計算。因此，共有$F_{n}+F_{n-1}$種方法來計算n的值。

• $F_{0}+F_{1}+F_{2}+F_{3}+...+F_{n}=F_{n+2}-1$

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

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

1. 若第1個被加數是2，有$F_{n}$種方法來計算加至$n-1$的方法的數目；
2. 若第2個被加數是2、第1個被加數是1，有$F_{n-1}$種方法來計算加至$n-2$的方法的數目。
3. 重複以上動作。
4. 若第$n+1$個被加數為2，它之前的被加數均為1，就有$F_{0}$種方法來計算加至0的數目。

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

• $F_{1}+2F_{2}+3F_{3}+...+nF_{n}=nF_{n+2}-F_{n+3}+2$

• $F_{1}+F_{3}+F_{5}+...+F_{2n-1}=F_{2n}$
• $F_{2}+F_{4}+F_{6}+...+F_{2n}=F_{2n+1}-1$
• ${F_{1}}^{2}+{F_{2}}^{2}+{F_{3}}^{2}+...+{F_{n}}^{2}=F_{n}F_{n+1}$
• $F_{n}F_{m-k}-F_{m}F_{n-k}=(-1)^{n-k}F_{m-n}F_{k}$，其中$m,n,k$與$F$的序數皆不限於正整數。
  • 特別地，當$n=m-k$時，${F_{n}}^{2}-F_{n+k}F_{n-k}=(-1)^{n-k}{F_{k}}^{2}$
    • 更特別地，當$k=1$或$k=-1$時，對於數列連續三項，有${F_{n}}^{2}-F_{n-1}F_{n+1}=(-1)^{n-1}$
  • 另一方面，當$(m,n,k)=(n+1,n,-2)$時，對於數列連續四項，有$F_{n}F_{n+3}-F_{n+1}F_{n+2}=(-1)^{n+1}$
  • ${F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}=F_{m+n-1}$（以$1$代入$k$，$1-n$代入$n$）
  • $F_{m}F_{n+1}+F_{m-1}F_{n}=F_{m+n}$

    特別地，當m = n時，${\begin{aligned}F_{2n-1}&=F_{n}^{2}+F_{n-1}^{2}\\F_{2n}&=(F_{n-1}+F_{n+1})F_{n}\\&=(2F_{n-1}+F_{n})F_{n}\end{aligned}}$

• $\varphi ^{n}=F_{n-1}+\varphi F_{n}$且$(1-\varphi )^{n}=F_{n+1}-\varphi F_{n}$，其中$\varphi$為黃金比例${\frac {1+{\sqrt {5}}}{2}}$，$n$為任意整數

數論性質

公因數和整除關係

• $F_{n}$整除$F_{m}$，若且唯若n整除m，其中n≧3。
• $\gcd(F_{m},F_{n})=F_{\gcd(m,n)}$
• 任意連續三個菲波那契數兩兩互質，亦即，對於每一個n，

gcd(F_n, F_n+1) = gcd(F_n, F_n+2) = gcd(F_n+1, F_n+2) = 1

斐波那契质数

主条目：斐波那契质数

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

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

如§ 公因數和整除關係所述，$F_{kn}$總能被$F_{n}$整除，故除$F_{4}=3$之外，任何斐氏質數的下標必同為質數。由於存在任意長的一列連續合数，斐氏數列中亦能找到連續任意多項全為合數。

大於$F_{6}=8$的斐氏數，必不等於質數加一或減一。

與其他數列的交集

斐波那契数列中，只有3個平方數：0、1、144。2001年，派特·奧蒂洛證明衹有有限多個斐氏數是完全冪。2006年，Y. Bugeaud、M. Mignotte、S. Siksek三人證明此種冪僅得0、1、8、144。

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

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

模n的週期性

主条目：皮萨诺周期

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

推廣

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

和盧卡斯數列的關係

$F_{n}L_{n}=F_{2n}$

反費波那西數列

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

$G_{n+2}=G_{n}-G_{n+1}$

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

即是$F_{2n+1}=G_{2n+1}=F_{-(2n+1)},F_{2n}=-G_{2n}=-F_{-2n}$，

亦可寫成$F_{m}=(-1)^{m+1}G_{m}=(-1)^{m+1}F_{-m}$，其中$m$是非負整數。

反費波那西數列兩項之間的比會趨近$-{\frac {1}{\varphi }}\approx -0.618$。

證明關係式

證明$F_{m}=(-1)^{m+1}F_{-m}$，其中$m$是非負整數

以$\varphi$表示黃金分割數${\frac {1+{\sqrt {5}}}{2}}$，則有$\varphi (1-\varphi )=-1$

故$(-1)^{m}=[\varphi (1-\varphi )]^{m}=\varphi ^{m}(1-\varphi )^{m}$，因此

${\begin{aligned}(-1)^{m+1}F_{-m}&=(-1)^{m+1}\times {\frac {1}{\sqrt {5}}}[\varphi ^{-m}-(1-\varphi )^{-m}]\\&=(-1)\times {\color {brown}(-1)^{m}}\times {\frac {1}{\sqrt {5}}}[\varphi ^{-m}-(1-\varphi )^{-m}]\\&=(-1)\times {\color {brown}\varphi ^{m}(1-\varphi )^{m}}\times {\frac {1}{\sqrt {5}}}[\varphi ^{-m}-(1-\varphi )^{-m}]\\&=(-1)\times {\frac {1}{\sqrt {5}}}[\varphi ^{-m+m}(1-\varphi )^{m}-(1-\varphi )^{-m+m}\varphi ^{m}]\\&=(-1)\times {\frac {1}{\sqrt {5}}}[(1-\varphi )^{m}-\varphi ^{m}]\\&={\frac {1}{\sqrt {5}}}[\varphi ^{m}-(1-\varphi )^{m}]\\&=F_{m}\\\end{aligned}}$

巴都萬數列

費波那西數列可以用一個接一個的正方形來表現，巴都萬數列則是用一個接一個的等邊三角形來表現，它有$P_{n}=P_{n-2}+P_{n-3}$的關係。

佩爾數列

佩爾數列的遞歸公式為$P_{n}=2P_{n-1}+P_{n-2}$，前幾項為0,1,2,5,12,29,70,169,408,...

應用

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

$y=F_{2x}$

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

電腦科學

高為6的斐波那契樹。平衡因子以綠色標記，節點的高度則為紅色。

最左一條路徑上的鍵值全為斐氏數。

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

程式參考

JavaScript迭代版

function fib(n) {
    var fib_n = function(curr, next, n) {
        if (n == 0) {
            return curr;
        }
        else {
            return fib_n(next, curr+next, n-1);
        }
    }
    return fib_n(0, 1, n);
}
alert(fib(40));

C语言通项公式版

#include <stdio.h>
#include <math.h>

int main()
{
    int n;
    double constant_a = (1 + sqrt(5)) / 2;
    double constant_b = (1 - sqrt(5)) / 2;
    double constant_c = sqrt(5) / 5;
    double value_1 = 0;
    int value_2 = 0;
    scanf("%d", &n);
    if(n > 0)
    {
        for (int i = 0; i < n; i++)
        {
             value_1 = constant_c * (pow(constant_a, i) - pow(constant_b, i));
             value_2 = (int)value_1;
             printf("%d\n", value_2);
        }
        return 0;
    }
    else
    {
        return -1;
    }
}

c++二變數求某項版

#include <iostream>
using namespace std;
int main () {
	int x,y,n;
    x=1;y=0;
	cin >> n;
	for (int i=0;i<n;i=i+1) {
	    x=x+y;
		y=x-y;
	}
	cout << y;
	return 0;
}

c++通项公式版

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    unsigned long long n;
    double ca = (1 + sqrt(5)) / 2;
    double cb = (1 - sqrt(5)) / 2;
    double cc = sqrt(5) / 5;
    double v1 = 0;
    double v2 = 0;
    cout <<" ";
    cin>>n;
    if(n > 0)
    {
        for (unsigned long long i = 0; i < n; i++)
    {
            v1 = cc * (pow(ca, i) - pow(cb, i));
        v2 = (int)v1;
        cout <<v2<<endl;
    }
    return 0;
    }
    else
    {
        return -1;
    }
        cout <<'/b';
}

Python语言通项公式版

# Fibonacci numbers module

def fib(n):    # write Fibonacci series up to n
    a, b = 0, 1
    while b < n:
        print(b, end=' ')
        a, b = b, a+b
    print()

def fib2(n):   # return Fibonacci series up to n
    result = []
    a, b = 0, 1
    while b < n:
        result.append(b)
        a, b = b, a+b
    return result

fibs = [0, 1]
numZS = int(input('How many Fibonacci numbers do you want? '))
for i in range(numZS-2):
    fibs.append(fibs[-2] + fibs[-1])
print fibs

Common Lisp

(defun fibs (x)
  (cond ((equal x 0) 1)
        ((equal x 1) 1)
        (t (+ (fibs (- x 1))
              (fibs (- x 2))))))

(defun fibs (x)
  (do ((n 0 (+ n 1))
       (i 1 j)
       (j 1 (+ i j)))
      ((equal n x) i)))

Go

遞迴版，時間複雜度為 O(2^n)：

func fibonacci(n int) int {
	if n < 2 {
		return n
	}

	return fibonacci(n-2) + fibonacci(n-1)
}

通用版，時間複雜度為 O(n)：

func fibonacci(n int) int {
	a, b := n%2, 1

	for i := 0; i < n/2; i++ {
		a += b
		b += a
	}

	return a
}

Java语言通项公式版：

public int fibonacci(int n){
    if(n<2){
     return n;
    }else {
      return fibonacci(n-1)+fibonacci(n-2);
    }
}

Java语言快捷版：

public int fibonacci(int n){
    if(n<2){
     return n;
    }else {
      int[] ans = new int[n];
          ans[0] = 1;
          ans[1] = 2;
          for(int i=2;i<n;i++) {
              ans[i]=ans[i-1]+ans[i-2];
          }
          return ans[n-1];
    }
}

C语言陣列版：

#include <stdio.h>
#include <stdlib.h> 
int main()
{   
     int n,s,L;
     printf("輸入長度");
     scanf("%d",&L);
     while(L<0)
     {
     	printf("錯誤"); 
     	return 0;
	 }
     int a[L]; 
     int x=1,y=2;
     a[0]=x;
     a[1]=x;
     a[2]=y;
	 for(n=3;n<L;n++)
	 {  
		 a[n]=a[n-1]+a[n-2];  	
	 }
       for(n=0;n<L;n++)
     {
         printf("%d ",a[n]);
     }
     system("pause");
     return 0;
}

Python Lambda 遞迴版:

fib = lambda n: n if n<2 else fib(n-1) + fib(n-2)

延伸閱讀

• 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皮科夫.數學之戀.湖南科技出版社.

參考文獻

• Livio, Mario. The Golden Ratio: The Story of Phi, the World's Most Astonishing Number First trade paperback. New York City: Broadway Books. 2003 [2002]. ISBN 0-7679-0816-3. 

參見

• 齊肯多夫定理

外部連結

• 費波那契數，孫智宏（pdf）
• Periods of Fibonacci Sequences Mod m at MathPages
• Scientists find clues to the formation of Fibonacci spirals in nature （页面存档备份，存于互联网档案馆）
• Fibonacci Sequence，In Our Time (BBC Radio 4)的《In Our Time》節目。(現在聆聽)
• Hazewinkel, Michiel (编), Fibonacci numbers, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4