費波那契數

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

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

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

• ${\displaystyle F_{0}=0}$
• ${\displaystyle F_{1}=1}$
• ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$（${\displaystyle n\geqq 2}$）

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

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

特別指出：0 不是第一項，而是第零項（${\displaystyle F_{0}}$）。

起源

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

兔子對的數量就是斐波那契數列

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

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

斐波納契數是楊輝三角的每一條紅色對角線上數字的和。

斐波納契數也是楊輝三角形（即帕斯卡三角形）的每一條紅色對角線上數字的和。

表達式

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

初等代數解法

已知：

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

首先構建等比數列

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

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

求出數列 { a n + α a n − 1 } {\displaystyle \left\{a_{n}+\alpha a_{n-1}\right\}}

由以上可得：
${\displaystyle {\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}}}$

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

求數列 { b n } {\displaystyle \left\{{b_{n}}\right\}} 進而得到 { a n } {\displaystyle \left\{a_{n}\right\}}

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

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

${\displaystyle 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]}$

用數學歸納法證明表達式

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

• 若${\displaystyle n}$為非負整數

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

當${\displaystyle n=1}$時，${\displaystyle {\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}}$，成立

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

當${\displaystyle n=k+2}$時

${\displaystyle {\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}}}$

亦成立

• 若${\displaystyle n}$為非正整數

當${\displaystyle n=0}$時，成立

當${\displaystyle n=-1}$時，${\displaystyle {\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}}$，成立

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

當${\displaystyle n=-k-2}$時

${\displaystyle {\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}}}$

亦成立

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

線性代數解法

${\displaystyle {\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}}}$

${\displaystyle {\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}}$

構建一個矩陣方程

設${\displaystyle J_{n}}$為第${\displaystyle n}$個月有生育能力的兔子數量，${\displaystyle A_{n}}$為這一月份的兔子數量。

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

上式表達了兩個月之間，兔子數目之間的關係。而要求的是，${\displaystyle A_{n+1}}$的表達式。

求矩陣的特徵值： λ {\displaystyle \lambda }

根據特徵值的計算公式，我們需要算出來 ${\displaystyle {\begin{vmatrix}-\lambda &1\\1&1-\lambda \\\end{vmatrix}}=0}$ 所對應的解。

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

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

特徵向量

將兩個特徵值代入

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

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

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

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

分解首向量

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

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

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

${\displaystyle {\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）

用數學歸納法證明

從

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

可得到

${\displaystyle {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）

${\displaystyle {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

${\displaystyle {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的基礎上，可以很快求出${\displaystyle A_{n+1}}$的表達式，將兩個特徵值代入6中

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

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

${\displaystyle 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）即為${\displaystyle A_{n+1}}$的表達式

數論解法

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

組合數解法

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

${\displaystyle 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}}$

黃金比例恆等式解法

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

此一般式對任意整數${\displaystyle n}$成立

近似值

當${\displaystyle n}$為足夠大的正整數時，則

${\displaystyle 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}}$

${\displaystyle 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}}$

用計算機求解

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

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

和黃金分割的關係

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

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

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

${\displaystyle {\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}}}}}}}}}$

${\displaystyle 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}}}}$

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

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

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

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

和自然的關係

更多資訊：自然界的圖案（英語：Patterns in nature）

參見：Golden ratio#Nature（英語：Golden ratio#Nature）

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

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

恆等式

資料來源：^[11]

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

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

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

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

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

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

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

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

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

• ${\displaystyle F_{1}+F_{3}+F_{5}+...+F_{2n-1}=F_{2n}}$
• ${\displaystyle F_{2}+F_{4}+F_{6}+...+F_{2n}=F_{2n+1}-1}$
• ${\displaystyle {F_{1}}^{2}+{F_{2}}^{2}+{F_{3}}^{2}+...+{F_{n}}^{2}=F_{n}F_{n+1}}$
• ${\displaystyle F_{n}F_{m-k}-F_{m}F_{n-k}=(-1)^{n-k}F_{m-n}F_{k}}$，其中${\displaystyle m,n,k}$與${\displaystyle F}$的序數皆不限於正整數。^{[註 2]}
  • 特別地，當${\displaystyle n=m-k}$時，${\displaystyle {F_{n}}^{2}-F_{n+k}F_{n-k}=(-1)^{n-k}{F_{k}}^{2}}$
    • 更特別地，當${\displaystyle k=1}$或${\displaystyle k=-1}$時，對於數列連續三項，有${\displaystyle {F_{n}}^{2}-F_{n-1}F_{n+1}=(-1)^{n-1}}$
  • 另一方面，當${\displaystyle (m,n,k)=(n+1,n,-2)}$時，對於數列連續四項，有${\displaystyle F_{n}F_{n+3}-F_{n+1}F_{n+2}=(-1)^{n+1}}$^{[註 3]}
• ${\displaystyle \varphi ^{n}=F_{n-1}+\varphi F_{n}}$且${\displaystyle (1-\varphi )^{n}=F_{n+1}-\varphi F_{n}}$，其中${\displaystyle \varphi }$為黃金比例${\displaystyle {\frac {1+{\sqrt {5}}}{2}}}$，${\displaystyle n}$為任意整數^{[註 1]}

藉由上述公式，又可推得以下恆等式^{[註 4]}：

• • ${\displaystyle {F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}=F_{m+n-1}}$^[11]
  • ${\displaystyle F_{m}F_{n+1}+F_{m-1}F_{n}=F_{m+n}}$^[11]

    特別地，當${\displaystyle m=n}$時，${\displaystyle {\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}}}$

數論性質

公因數和整除關係

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

${\displaystyle \mathrm {gcd} (F_{n},F_{n+1})=\mathrm {gcd} (F_{n},F_{n+2})=\mathrm {gcd} (F_{n+1},F_{n+2})=1}$

費波那契質數

主條目：費波那契質數

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

截至2015年，已知最大的費波那契質數是第104911個費波那契數，一共有21925個十進制位。不過，人們仍不知道是不是有無限個費波那契質數。^[13]

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

大於${\displaystyle F_{6}=8}$的斐氏數，必不等於質數加一或減一。^[14]

與其他數列的交集

斐波那契數列中，只有3個平方數：0、1、144。^[15][16]2001年，派特·奧蒂洛（匈牙利語：Pethő Attila）證明，斐氏數中的次方數衹有有限多個。^[17]2006年，Y. Bugeaud、M. Mignotte、S. Siksek三人證明，費波那契數中的次方數只有0、1、8、144。^[18]

1、3、21、55為僅有的斐氏三角形數。Vern Hoggatt（英語：Verner Emil Hoggatt Jr.）曾猜想此結論，後來由羅明證明。^[19]

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

模n的週期性

主條目：皮薩諾週期

斐波那契數列各項模${\displaystyle n}$的餘數構成週期數列（英語：periodic sequence），其最小正週期稱為皮薩諾週期^[23]，至多為${\displaystyle 6n}$^[24]。皮薩諾週期對不同${\displaystyle n}$值的通項公式仍是未解問題，其中一步需要求出某個整數（同餘意義下）或二次有限體元素的乘法階數（英語：multiplicative order）。不過，對固定的${\displaystyle n}$，求解模${\displaystyle n}$的皮薩諾週期是週期檢測（英語：cycle detection）問題的特例。

推廣

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

和盧卡斯數列的關係

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

反費波那西數列

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

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

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

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

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

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

證明關係式

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

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

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

${\displaystyle {\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}}}$

巴都萬數列

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

佩爾數列

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

應用

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

${\displaystyle y=F_{2x}}$

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

電腦科學

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

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

• 考慮以輾轉相除法求兩個正整數的最大公因數，分析此算法的運行時間。同等輸入規模下，最壞情況（用時最長）發生於輸入為兩個相鄰斐氏數時。^[25]
• 歸併排序算法有一多相（polyphase）版本用到斐氏數列，是將未排序的數組分為兩份，長度為相鄰的斐氏數（因此比值接近黃金比）。《電腦程式設計藝術》^{[頁碼請求]}描述了此種多相合併排序（英語：polyphase merge sort）的實作方法，適用於以磁帶機為外存的情況。
• 費波那契樹是一棵二叉樹，其每個節點的左右子樹高皆恰好差1。由此，斐氏樹為AVL樹，且對固定高度而言，是最少節點的AVL樹。此類樹的節點數可寫成斐氏數減1。^[26]
• 某些偽隨機數生成器用到斐氏數列。^{[具體情況如何？]}
• 費波那契堆是一種數據結構，分析其時間複雜度時會用到費波那契數。
• 費波那契編碼是以01字串表示正整數的一種方法，負費波那契編碼（英語：NegaFibonacci coding）與之類似，還可以表示負數。

延伸閱讀

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

參考文獻

1. 斐波那契数列与组合数的一个关系及推广. [2014-01-04]. （原始內容存檔於2019-05-02）.
2. Douady, S; Couder, Y. Phyllotaxis as a Dynamical Self Organizing Process (PDF). Journal of Theoretical Biology. 1996, 178 (3): 255–74. ISSN 0022-5193. doi:10.1006/jtbi.1996.0026. （原始內容 (PDF)存檔於2006-05-26）.
3. Jones, Judy; Wilson, William. Science. An Incomplete Education. Ballantine Books. 2006: 544. ISBN 978-0-7394-7582-9.
4. Brousseau, A. Fibonacci Statistics in Conifers. Fibonacci Quarterly（英語：Fibonacci Quarterly）. 1969, (7): 525–32.
5. Marks for the da Vinci Code: B–, Maths (Computer Science For Fun: CS4FN), [2022-10-30], （原始內容存檔於2009-05-31）
6. Scott, T.C.; Marketos, P., On the Origin of the Fibonacci Sequence (PDF), MacTutor History of Mathematics archive, University of St Andrews, 2014-03 [2022-10-30], （原始內容存檔 (PDF)於2019-09-18）
7. Livio 2003，第110頁.
8. Livio 2003，第112–13頁.
9. Varenne, Franck. Formaliser le vivant - Lois, Théories, Modèles. Hermann. 2010-11-16: 28 [2022-10-30]. ISBN 9782705678128. （原始內容存檔於2022-10-30）.
10. The Secret of the Fibonacci Sequence in Trees. 美國自然史博物館. 2011 [2019-02-04]. （原始內容存檔於2013-05-04）.
11. 李晨滔、馮勁敏. 費氏數列的性質整理 (PDF). 桃園縣立大園國際高中. [2018-01-28]. （原始內容存檔 (PDF)於2019-06-25）.
12. Sloane, N.J.A. (編). Sequence A005478. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
13. Weisstein, Eric W. (編). Fibonacci Prime. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.
14. Honsberger, Ross. Mathematical Gems III. AMS Dolciani Mathematical Expositions. 1985, (9): 133. ISBN 978-0-88385-318-4.
15. JOHN H. E. COHN. Square Fibonacci Numbers, Etc.. Bedford College, University of London, London, N.W.1. [2019-05-12]. （原始內容存檔於2012-06-30）. Theorem 3. If F_n = x², then n = 0, ±1, 2 or 12.
16. Cohn, J. H. E., On square Fibonacci numbers, The Journal of the London Mathematical Society, 1964, 39: 537–540, MR 0163867, doi:10.1112/jlms/s1-39.1.537
17. Pethő, Attila. Diophantine properties of linear recursive sequences II. Acta Mathematica Academiae Paedagogicae Nyíregyháziensis. 2001, 17: 81–96. MR 1887650.
18. Bugeaud, Y; Mignotte, M; Siksek, S. Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers. Ann. Math. 2006, 2 (163): 969–1018. Bibcode:2004math......3046B. MR 2215137. S2CID 10266596. arXiv:math/0403046 . doi:10.4007/annals.2006.163.969.
19. Luo, Ming. On triangular Fibonacci numbers (PDF). Fibonacci Quart. 1989, 27 (2): 98–108 [2022-10-29]. MR 0995557. （原始內容存檔 (PDF)於2022-10-29）.
20. Luca, Florian. Perfect Fibonacci and Lucas numbers. Rendiconti del Circolo Matematico di Palermo. 2000, 49 (2): 313–18. ISSN 1973-4409. MR 1765401. S2CID 121789033. doi:10.1007/BF02904236.
21. Broughan, Kevin A.; González, Marcos J.; Lewis, Ryan H.; Luca, Florian; Mejía Huguet, V. Janitzio; Togbé, Alain. There are no multiply-perfect Fibonacci numbers. Integers. 2011, 11a: A7 [2022-10-29]. MR 2988067. （原始內容存檔於2022-01-23）.
22. Luca, Florian; Mejía Huguet, V. Janitzio. On Perfect numbers which are ratios of two Fibonacci numbers. Annales Mathematicae at Informaticae. 2010, 37: 107–24. ISSN 1787-6117. MR 2753031.
23. Sloane, N.J.A. (編). Sequence A001175. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
24. Freyd, Peter; Brown, Kevin S. Problems and Solutions: Solutions: E3410. The American Mathematical Monthly. 1993, 99 (3): 278–79. JSTOR 2325076. doi:10.2307/2325076.
25. Knuth, Donald E. The Art of Computer Programming. 1: Fundamental Algorithms 3rd. Addison–Wesley. 1997: 343. ISBN 978-0-201-89683-1.
26. Adelson-Velsky, Georgy; Landis, Evgenii. An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences（英語：Proceedings of the USSR Academy of Sciences）. 1962, 146: 263–266 （俄語）. Myron J. Ricci 的英文翻譯 （頁面存檔備份，存於互聯網檔案館）載於 Soviet Mathematics - Doklady, 3:1259–1263, 1962.

• 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] [2022-10-30]. ISBN 0-7679-0816-3. （原始內容存檔於2023-03-13）.

註釋

1. 這可以透過${\displaystyle \varphi ^{2}=1+\varphi }$與${\displaystyle {\frac {1}{\varphi }}=\varphi -1}$與${\displaystyle {\frac {1}{1-\varphi }}=-\varphi }$此三個等式，以及斐波那契數列的遞歸定義，以數學歸納法證明。
2. 例如當${\displaystyle (m,n,k)=(4,-8,6)}$時，${\displaystyle F_{-8}F_{-2}-F_{4}F_{-14}=(-21)\times (-1)-3\times (-377)=(-1)^{-14}F_{12}F_{6}=1\times 144\times 8=1152}$
3. 亦即「頭尾兩項乘積」與「中間兩項乘積」恆相差1
4. 利用指數律${\displaystyle \varphi ^{m+n}=\varphi ^{m}\times \varphi ^{n}}$、性質${\displaystyle \varphi ^{2}=1+\varphi }$，以及「若${\displaystyle a,b,c,d}$是有理數，${\displaystyle x}$是無理數，且滿足${\displaystyle a+bx=c+dx}$，則${\displaystyle a=c,b=d}$」證明。

參見

• 齊肯多夫定理

外部連結

• 費波那契數，孫智宏（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)（英語：BBC Radio 4）的《In Our Time》節目。(現在聆聽)
• Hazewinkel, Michiel (編), Fibonacci numbers, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4