查看“︁斐波那契数”︁的源代码

{{refimprove|time=2014-03-25T08:24:56+00:00}}
{{NoteTA
|G1=Math
|1=zh-cn:程序; zh-tw:程式;
|2=zh-tw:費波那契;zh-hk:費波那契;zh-cn:斐波那契;
}}

[[File:34*21-FibonacciBlocks.png|thumb|400px|以斐波那契數為邊的正方形拼成的近似的[[黃金矩形]](1:1.618)]]

'''-{zh-hant:費波那契數;zh-hans:斐波那契数}-'''（[[意大利语]]：Numero di Fibonacci），又譯為'''菲波拿契數'''、'''菲波那西數'''、'''斐氏數'''、'''黃金分割數、費氏數列'''。所形成的[[數列]]稱為'''-{zh-hant:費波那契數列;zh-hans:斐波那契数列}-'''（[[意大利语]]：Successione di Fibonacci），又譯為'''菲波拿契數列'''、'''菲波那西數列'''、'''斐氏數列'''、'''黃金分割數列、費氏數列'''。這個數列是由[[意大利]][[數學家]][[斐波那契]]在他的《算盤書》中提出。

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

*<math>F_0=0</math>
*<math>F_1=1</math>
*<math>F_n = F_{n-1}+ F_{n-2}</math>（<math>n\geqq 2</math>）

用白話文來說，就是斐波那契數列由0和1開始，之後的斐波那契數就是由之前的兩數相加而得出。首幾個斐波那契數是：
:{{數列|[[$]]、 |1|15|last(1)+last(2)|last1=1}}987……{{OEIS|id=A000045}}

'''特別指出'''：[[0]] 不是第一項，而是第零項（<math>F_0</math>）。
{{TOClimit|limit=3}}

==起源==
公元1150年[[印度]][[數學家]][[Gopala]]和[[金月]]在研究[[箱子包裝問題|箱子包裝]]物件長宽剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是[[比薩的李奧納多]]（意大利人斐波那契Leonardo Fibonacci, 1175－1250），他描述[[兔子]]生長的數目時用上了這數列：
[[File:FibonacciRabbit.svg|thumb|300px|兔子对的数量就是斐波那契数列]]
*第一個月初有一對剛誕生的兔子
*第二個月之後（第三個月初）牠們可以生育
*每月每對可生育的兔子會誕生下一對新兔子
*兔子永不死去
假設在<math>n</math>月有兔子總共<math>a</math>對，<math>n+1</math>月總共有<math>b</math>對。在<math>n+2</math>月必定總共有<math>a+b</math>對：因為在<math>n+2</math>月的時候，前一月（<math>n+1</math>月）的<math>b</math>對兔子可以存留至第<math>n+2</math>月（在當月屬於新誕生的兔子尚不能生育）。而新生育出的兔子對數等於所有在<math>n</math>月就已存在的<math>a</math>對
[[File:PascalTriangleFibanacci.svg|thumb|300px|斐波纳契数是杨辉三角的每一条红色对角线上数字的和。]]
斐波纳契数也是[[杨辉三角形]]（即帕斯卡三角形）的每一条红色对角线上数字的和。

==表達式==
為求得斐波那契數列的一般表達式，可以藉助線性代數的方法。高中的初等數學知識也能求出。
===初等代數解法===
已知：
*<math>a_1=1</math>
*<math>a_2=1</math>
*<math>a_n = a_{n-1}+ a_{n-2}</math>（n≥3）

====首先構建等比數列====
設<math>a_n +\alpha a_{n-1}=\beta (a_{n-1}+\alpha  a_{n-2})</math><br />化簡得<br /><math>a_n=(\beta -\alpha) a_{n-1}+ \alpha\beta a_{n-2}</math><br />
比較係數可得：<br />
<math> \begin{cases}
\beta-\alpha=1 \\
\alpha\beta=1
\end{cases}</math>
<br />不妨設<math>\beta>0,  \alpha>0</math><br />
解得：<br />

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

====求出數列<math>\left\{ a_n +\alpha a_{n-1} \right\}</math>====
由以上可得：<br />
<math>\begin{align}a_{n+1} +\alpha a_{n} &=(a_2+\alpha a_1)\beta^{n-1}\\
& = (1+\alpha)\beta^{n-1}\\
& =\beta^n \\
\end{align}
</math><br />

變形得：
<math>\frac{a_{n+1}}{\beta^{n+1}}+\frac{\alpha}{\beta}\cdot\frac{a_{n}}{\beta^{n}}=\frac{1}{\beta}</math>。
令<math>b_n=\frac{a_n}{\beta^n}</math>

==== 求數列<math>\left \{ {b_n} \right \}</math>進而得到<math>\left \{ a_n \right \}</math>====
<math>b_{n+1}+\frac{\alpha}{\beta}b_{n}=\frac{1}{\beta}</math><br />
設<math>b_{n+1}+\lambda=-\frac{\alpha}{\beta} (b_{n}+\lambda)</math>，解得<math>\lambda=-\frac{1}{\alpha+\beta}</math>。
故數列<math>\left\{b_n+\lambda\right\}</math>為等比數列<br />
即<math>b_n+\lambda=\left(-\frac{\alpha}{\beta}\right)^{n-1}\left(b_1+\lambda\right)</math>。而<math>b_1=\frac{a_1}{\beta}=\frac{1}{\beta}</math>，
故有<math>b_n+\lambda=\left(-\frac{\alpha}{\beta}\right)^{n-1}\left(\frac{1}{\beta}+\lambda\right)</math><br />
又有<math> \begin{cases}
\alpha=\dfrac{\sqrt{5}-1}{2} \\
\beta=\dfrac{\sqrt{5}+1}{2}
\end{cases}</math>
和<math>b_n=\frac{a_n}{\beta^n}</math><br />
可得<math>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]</math>

得出<math>{a_n}</math>表達式<br />

<math>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]</math>

=== 用數學歸納法證明表達式 ===
;證明<math>F_n=\frac{1}{\sqrt{5}}[\varphi^n-(1-\varphi)^n]</math>，其中<math>\varphi</math>為[[黃金比例]]<math>\frac{1+\sqrt{5}}{2}</math>，<math>n</math>為任意整數
*若<math>n</math>為非負整數
:當<math>n=0</math>時，<math>\frac{1}{\sqrt{5}}[\varphi^0-(1-\varphi)^0]=\frac{1}{\sqrt{5}}[1-1]=0=F_0</math>，成立
:當<math>n=1</math>時，<math>\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</math>，成立
:設當<math>n=k</math>及<math>n=k+1</math>時皆成立，即<math>F_k=\frac{1}{\sqrt{5}}[\varphi^k-(1-\varphi)^k]</math>且<math>F_{k+1}=\frac{1}{\sqrt{5}}[\varphi^{k+1}-(1-\varphi)^{k+1}]</math>
:當<math>n=k+2</math>時
:<math>
\begin{align}
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{align}
</math>
:亦成立
*若<math>n</math>為非正整數
:當<math>n=0</math>時，成立
:當<math>n=-1</math>時，<math>\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}</math>，成立
:設當<math>n=-k</math>及<math>n=-k-1</math>時皆成立，即<math>F_{-k}=\frac{1}{\sqrt{5}}[\varphi^{-k}-(1-\varphi)^{-k}]</math>且<math>F_{-k-1}=\frac{1}{\sqrt{5}}[\varphi^{-k-1}-(1-\varphi)^{-k-1}]</math>
:當<math>n=-k-2</math>時
:<math>
\begin{align}
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{align}
</math>
:亦成立

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

===線性代數解法===
<math>
\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}
</math>

<math>
\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}
</math>
====構建一個矩陣方程====

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

:<math>{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} \cdot {J_n\choose A_{n}},</math>

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

====求矩陣的[[特徵值]]：<math> \lambda </math>====

根据[[:特征值和特征向量#计算矩阵的特征值和特征向量|特征值的计算公式]]，我们需要算出来 <math>
\begin{vmatrix}
  -\lambda & 1 \\
  1 & 1 - \lambda \\
\end{vmatrix} = 0
</math> 所对应的解。

展开行列式有：<math>-\lambda(1-\lambda)-1\times1=\lambda^2-\lambda-1</math>。

故當行列式的值為 0，解得 <math> \lambda_1 =\frac{1}{2} (1 + \sqrt{5})</math> 或 <math> \lambda_2 =\frac{1}{2} (1 - \sqrt{5})</math>。

====[[特徵向量]]====
將兩個特徵值代入

: <math>\left(\begin{pmatrix}0&1\\1&1\end{pmatrix}-\lambda \cdot E\right) \cdot\vec x = 0</math> 


求特徵向量<math>\vec x</math>得

<math>\vec x_1</math>=<math>\begin{pmatrix} 1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}</math>

<math>\vec x_2</math>=<math>\begin{pmatrix} 1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}</math>

====分解首向量====
第一個月的情況是兔子一對，新生0對。

:<math>{J_{1}\choose A_{1}} = \begin{pmatrix}0\\1\end{pmatrix}</math>

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

:<math>\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}</math>  （4）

====用[[數學歸納法]]證明====

從
:<math>{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix}

 \cdot {J_n\choose A_{n}}</math>=<math>\lambda \cdot {J_n\choose A_{n}}</math>

可得到

:<math>{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}}</math>  （5）

====化簡矩陣方程====

將（4） 代入 （5）

:<math>{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]</math>

根據3
:<math>{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}</math>

====求A的表達式====
現在在6的基礎上，可以很快求出<math>A_{n+1}</math>的表達式，將兩個特徵值代入6中

:<math>A_{n+1}=\frac{1}{\sqrt{5}} \cdot \lambda_1^{n+1} - \frac{1}{\sqrt{5}} \cdot \lambda_2^{n+1}</math>

:<math>A_{n+1}=\frac{1}{\sqrt{5}} \cdot (\lambda_1^{n+1} -  \lambda_2^{n+1})</math>

:<math>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\}</math>（7）

（7）即為<math>A_{n+1}</math>的表達式

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

===組合數解法===
<math> F_n=\sum_{i=0}^{\infty} \binom {n-i}{i}</math><ref>{{cite web|url=http://www.cnki.com.cn/Article/CJFDTotal-ZXJI199110005.htm|title=斐波那契数列与组合数的一个关系及推广|access-date=2014-01-04|archive-date=2019-05-02|archive-url=https://web.archive.org/web/20190502172414/http://www.cnki.com.cn/Article/CJFDTotal-ZXJI199110005.htm|dead-url=no}}</ref>
: <math> 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}</math>

===黃金比例恆等式解法===
設<math>\varphi</math>為[[黃金比例]]<math>\frac{1+\sqrt{5}}{2}</math>，則有[[恆等式]]<math>\varphi^n=F_{n-1}+\varphi F_n</math>與<math>(1-\varphi)^n=F_{n+1}-\varphi F_n</math>，其中<math>n</math>為任意整數{{NoteTag|name=varphi}}，則

<math>
\begin{align}
\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{align}
</math>

因此得到<math>F_n</math>的一般式：

<math>
\begin{align}
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{align}
</math>

此一般式對任意整數<math>n</math>成立

===近似值===
當<math>n</math>為足夠大的正整數時，则
:<math>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 </math>
:<math>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} </math>

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

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

==和黃金分割的關係==
[[開普勒]]發現數列前、後兩項之比<math>\frac{1}{2}, \frac{2}{3}, \frac{3}{5}, \frac{5}{8}, \frac{8}{13}, \frac{13}{21}, \frac{21}{34}, \cdots </math>，也組成了一個數列，會趨近[[黃金分割]]：

:<math>\frac {f_{n+1}}{f_n} \approx a = \frac{1}{2} (1 + \sqrt{5}) = \varphi \approx 1{.}618{...}</math>

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

<math>\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}}}}</math>

<math>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}}</math>

而黃金分割數亦可以用無限連分數表示：
:<math>\varphi = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1+ ...}}}}</math>
而黃金分割數也可以用無限多重根號表示：
:<math>\varphi=\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+...}}}}</math>

==和自然的關係==

{{Further |{{le|自然界的圖案|Patterns in nature}}}}
{{see also|{{le|Golden ratio#Nature}}}}
[[File:FibonacciChamomile.PNG|thumb|[[春黄菊]]的[[頭狀花序]]上，小花呈螺旋狀排列，從不同方向可以數出21（深藍）和13（淺藍）條旋臂，為相鄰的斐氏數。類似的螺旋狀排列見於多種植物。]]

斐氏數列見於不同的生物學現象<ref>{{cite journal |first1=S |last1=Douady |first2=Y |last2=Couder |title=Phyllotaxis as a Dynamical Self Organizing Process |journal=Journal of Theoretical Biology |year=1996 |issue=3 |pages=255–74 |url=http://www.math.ntnu.no/~jarlet/Douady96.pdf |doi=10.1006/jtbi.1996.0026 |volume=178 |url-status=dead |archive-url=https://web.archive.org/web/20060526054108/http://www.math.ntnu.no/~jarlet/Douady96.pdf |archive-date=2006-05-26 |issn = 0022-5193 }}</ref>，如樹的分枝、{{link-en|葉序|Phyllotaxis|葉在枝條上的排列}}、菠蘿[[聚花果]]上小單果的排列、<ref>{{cite book | first1=Judy |last1=Jones | first2=William | last2=Wilson |title=An Incomplete Education | url=https://archive.org/details/incompleteeducat0003jone |publisher=Ballantine Books |year=2006 |isbn=978-0-7394-7582-9 |page=[https://archive.org/details/incompleteeducat0003jone/page/544 544] |chapter=Science}}</ref>[[雅枝竹]]的花蕾、正在舒展的蕨葉、[[松毬]]的鱗的排列<ref>{{cite journal| first=A | last=Brousseau |title=Fibonacci Statistics in Conifers | journal={{link-en|斐波那契季刊|Fibonacci Quarterly|Fibonacci Quarterly}} |year=1969 |issue=7 |pages=525–32}}</ref>、蜜蜂的家族樹<ref>{{citation |url = http://www.cs4fn.org/maths/bee-davinci.php |work = Maths |publisher = Computer Science For Fun: CS4FN |title = Marks for the da Vinci Code: B– |accessdate = 2022-10-30 |archive-date = 2009-05-31 |archive-url = https://web.archive.org/web/20090531091345/http://www.cs4fn.org/maths/bee-davinci.php |dead-url = no }}</ref><ref>{{Citation|first1=T.C.|last1=Scott|first2=P.|last2=Marketos|url=http://www-history.mcs.st-andrews.ac.uk/Publications/fibonacci.pdf|title=On the Origin of the Fibonacci Sequence|publisher=[[MacTutor数学史档案|MacTutor History of Mathematics archive]], University of St Andrews|date=2014-03|accessdate=2022-10-30|archive-date=2019-09-18|archive-url=https://web.archive.org/web/20190918155822/http://www-history.mcs.st-andrews.ac.uk/Publications/fibonacci.pdf|dead-url=no}}</ref>。[[约翰内斯·开普勒|开普勒]]曾指出斐氏數列存在於自然界，並以此解釋某些花的五邊形形態（與[[黄金分割率]]相關）。{{sfn|Livio|2003|p=110}}[[法國菊]]的「瓣」（舌狀花）數通常為斐氏數。{{sfn|Livio|2003|pp=112–13}}1830年，K. F. Schimper和A. Braun發現植物的旋生葉序中，連續兩塊葉之間轉過的角度與周角之比，約成整數比時，常出現斐氏數<ref>{{Cite book| first = Franck| last = Varenne| title = Formaliser le vivant - Lois, Théories, Modèles| accessdate = 2022-10-30| url = https://www.numilog.com/LIVRES/ISBN/9782705670894.Livre?utm_source=PDF-excerpt| page = 28| date = 2010-11-16| isbn = 9782705678128| publisher = Hermann| archive-date = 2022-10-30| archive-url = https://web.archive.org/web/20221030223449/https://www.numilog.com/LIVRES/ISBN/9782705670894.Livre?utm_source=PDF-excerpt| dead-url = no}}</ref>，如<math>2/5</math>或<math>5/13</math><ref>{{cite website|url=http://www.amnh.org:80/learn-teach/young-naturalist-awards/winning-essays/2011/the-secret-of-the-fibonacci-sequence-in-trees|title=The Secret of the Fibonacci Sequence in Trees|year=2011|website=[[美國自然史博物館]]|archive-url=https://web.archive.org/web/20130504125059/http://www.amnh.org/learn-teach/young-naturalist-awards/winning-essays/2011/the-secret-of-the-fibonacci-sequence-in-trees|archive-date=2013-05-04|access-date=2019-02-04|url-status=live}}</ref>。

==恆等式==
<small>資料來源：</small><ref name="性質整理">{{cite web|url=http://www.shs.edu.tw/works/essay/2014/03/2014032310331517.pdf|author=李晨滔、馮勁敏|title=費氏數列的性質整理|publisher=桃園縣立大園國際高中|access-date=2018-01-28|archive-date=2019-06-25|archive-url=https://web.archive.org/web/20190625225103/https://www.shs.edu.tw/works/essay/2014/03/2014032310331517.pdf|dead-url=no}}</ref>

證明以下的恆等式有很多方法。以下會用[[組合論述]]來證明。
* <math>F_n</math>可以表示用多個1和多個2相加令其和等於<math>n</math>的方法的數目。
[[不失一般性]]，我們假設<math>n\geq1</math>，<math>F_{n+1}</math>是計算了將1和2加到n的方法的數目。若第一個被加數是1，有<math>F_n</math>種方法來完成對<math>n-1</math>的計算；若第一個被加數是2，有<math>F_{n-1}</math>來完成對<math>n-2</math>的計算。因此，共有<math>F_n + F_{n-1}</math>種方法來計算n的值。
* <math>F_0 + F_1 + F_2 + F_3 + ... + F_n = F_{n+2} - 1 </math>
計算用多個1和多個2相加令其和等於<math>n+1</math>的方法的數目，同時至少一個加數是2的情況。

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

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

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

*<math>F_1 + 2 F_2 + 3 F_3 + ... + n F_n = n F_{n + 2} - F_{n + 3} + 2</math> 

*<math>F_1 + F_3 + F_5 + ... + F_{2n-1} = F_{2n}</math>
*<math>F_2 + F_4 + F_6 + ... + F_{2n} = F_{2n+1} - 1</math>
*<math>{F_1}^2 + {F_2}^2 + {F_3}^2 + ... + {F_n}^2 = F_n F_{n+1}</math>
*<math>F_nF_{m-k}-F_mF_{n-k}=(-1)^{n-k}F_{m-n}F_k</math>，其中<math>m,n,k</math>與<math>F</math>的序數皆不限於正整數。{{NoteTag|例如當<math>(m,n,k)=(4,-8,6)</math>時，<math>F_{-8}F_{-2}-F_4F_{-14}=(-21) \times (-1)-3 \times (-377)=(-1)^{-14}F_{12}F_6=1 \times 144 \times 8=1152</math>}}
**特別地，當<math>n=m-k</math>時，<math>{F_n}^2-F_{n+k} F_{n-k} = (-1)^{n-k}{F_k}^2</math>
***更特別地，當<math>k=1</math>或<math>k=-1</math>時，對於數列連續三項，有<math>{F_n}^2-F_{n-1} F_{n+1} = (-1)^{n-1}</math>
**另一方面，當<math>(m,n,k)=(n+1,n,-2)</math>時，對於數列連續四項，有<math>F_nF_{n+3}-F_{n+1}F_{n+2}=(-1)^{n+1}</math>{{NoteTag|亦即「頭尾兩項乘積」與「中間兩項乘積」恆相差1}}
*<math>\varphi^n=F_{n-1}+\varphi F_n</math>且<math>(1-\varphi)^n=F_{n+1}-\varphi F_n</math>，其中<math>\varphi</math>為[[黃金比例]]<math>\frac{1+\sqrt{5}}{2}</math>，<math>n</math>為任意整數{{NoteTag|name=varphi|1=這可以透過<math>\varphi^2=1+\varphi</math>與<math>\frac{1}{\varphi}=\varphi-1</math>與<math>\frac{1}{1-\varphi}=-\varphi</math>此三個等式，以及費氏數列的遞歸定義，以[[數學歸納法]]證明。}}
::藉由上述公式，又可推得以下恆等式{{NoteTag|利用指數律<math>\varphi^{m+n}=\varphi^m \times \varphi^n</math>、性質<math>\varphi^2=1+\varphi</math>，以及「若<math>a,b,c,d</math>是有理數，<math>x</math>是無理數，且滿足<math>a+bx=c+dx</math>，則<math>a=c,b=d</math>」證明。}}：
**<math>{F_m}{F_n} + {F_{m-1}}{F_{n-1}} = F_{m+n-1}</math><ref name="性質整理"/>
**<math>F_{m} F_{n+1} + F_{m-1} F_n = F_{m+n}</math><ref name="性質整理"/><p>特別地，當<math>m=n</math>時，<math>\begin{align}
 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{align}</math></p>

== 數論性質 ==
=== 公因數和整除關係 ===
*<math>F_n</math>整除<math>F_m</math>，若且唯若<math>n</math>整除<math>m</math>，其中<math>n\geqq 3</math>。
*<math>\gcd(F_m,F_n)=F_{\gcd(m,n)}</math>
*任意連續三個菲波那契數兩兩[[互質]]，亦即，對於每一個<math>n</math>，
:<math>\mathrm{gcd}(F_n, F_{n+1})=\mathrm{gcd}(F_n, F_{n+2})=\mathrm{gcd}(F_{n+1}, F_{n+2})=1</math>

===斐波那契质数===
{{main|斐波那契质数}}
在斐波那契數列中，有[[質數]]：<ref>{{Cite OEIS|1=A005478}}</ref>
2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……

截至2015年，已知最大的斐波那契質數是第104911個斐波那契數，一共有21925個十進制位。不过，人们仍不知道是不是有无限个斐波那契质数。<ref>{{cite mathworld |urlname=FibonacciPrime |title=Fibonacci Prime}}</ref>

如{{section link|#公因數和整除關係}}所述，<math>F_{kn}</math>總能被<math>F_n</math>整除，故除<math>F_4 = 3</math>之外，任何斐氏質數的下標必同為質數。由於存在{{link-en|任意大|Arbitrarily large|任意長}}的一列連續[[合数]]，斐氏數列中亦能找到連續任意多項全為合數。

大於<math>F_6 = 8</math>的斐氏數，必不等於質數加一或減一。<ref>{{cite journal | first = Ross | last = Honsberger | title = Mathematical Gems III | journal = AMS Dolciani Mathematical Expositions | year = 1985 | isbn = 978-0-88385-318-4 | page = 133 | issue = 9}}</ref>

=== 與其他數列的交集 ===
斐波那契数列中，只有3個[[平方數]]：[[0]]、[[1]]、[[144]]。<ref>{{cite web|author=JOHN H. E. COHN|title=Square Fibonacci Numbers, Etc.|url=https://math.la.asu.edu/~checkman/SquareFibonacci.html|publisher=Bedford College, University of London, London, N.W.1.|archiveurl=https://archive.today/20120630214035/http://math.la.asu.edu/~checkman/SquareFibonacci.html|archivedate=2012-06-30|quote=<u>Theorem 3.</u> If F<sub>n</sub> = x<sup>2</sup>, then n = 0, ±1, 2 or 12.|access-date=2019-05-12}}</ref><ref>{{citation | last = Cohn | first = J. H. E. | doi = 10.1112/jlms/s1-39.1.537 | journal = The Journal of the London Mathematical Society | mr = 163867 | pages = 537–540 | title = On square Fibonacci numbers | volume = 39 | year = 1964}}</ref>2001年，{{link-hu|派特·奧蒂洛|Pethő Attila}}<!--WP:外語譯音表/匈牙利語-->證明，斐氏數中的[[次方數]]衹有有限多個。<ref>{{cite journal | first = Attila | last = Pethő | title = Diophantine properties of linear recursive sequences II | journal = Acta Mathematica Academiae Paedagogicae Nyíregyháziensis | volume = 17 | year = 2001 | pages = 81–96|mr = 1887650}}</ref>2006年，Y. Bugeaud、M. Mignotte、S. Siksek三人證明，斐波那契数中的次方數只有0、1、8、144。<ref>{{cite journal|first1=Y|last1=Bugeaud|first2=M|last2= Mignotte|first3=S|last3=Siksek|title = Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers | journal = Ann. Math.|volume = 2 | year = 2006 | pages = 969–1018 | issue = 163 | bibcode = 2004math......3046B | arxiv = math/0403046| doi = 10.4007/annals.2006.163.969|s2cid=10266596|mr = 2215137}}</ref>

1、3、21、55為僅有的斐氏[[三角形數]]。{{link-en|Vern Hoggatt|Verner Emil Hoggatt Jr.|Vern Hoggatt}}曾猜想此結論，後來由罗明<!--https://www.cqnu.edu.cn/info/1023/4539.htm -->證明。<ref>{{cite journal | last = Luo | first = Ming | title = On triangular Fibonacci numbers | journal = Fibonacci Quart. | volume = 27 | issue = 2 | year = 1989 | pages = 98–108 | url = http://www.fq.math.ca/Scanned/27-2/ming.pdf | mr = 0995557 | access-date = 2022-10-29 | archive-date = 2022-10-29 | archive-url = https://web.archive.org/web/20221029210842/https://www.fq.math.ca/Scanned/27-2/ming.pdf | dead-url = no }}</ref>

斐波那契數不能為[[完全数]]。<ref name="Luca2000">{{cite journal | first=Florian | last=Luca | title=Perfect Fibonacci and Lucas numbers | journal=Rendiconti del Circolo Matematico di Palermo | year=2000 | volume=49 | issue=2 | pages=313–18 | doi=10.1007/BF02904236 | mr=1765401 | s2cid=121789033 | issn=1973-4409 }}</ref>推而廣之，除1之外，其他斐氏數皆非[[多重完全數]]<ref name="BGLLHT2011">{{cite journal | first1=Kevin A. | last1=Broughan | first2=Marcos J. | last2=González | first3=Ryan H. | last3=Lewis | first4=Florian | last4=Luca | first5=V. Janitzio | last5=Mejía Huguet | first6=Alain | last6=Togbé | title=There are no multiply-perfect Fibonacci numbers | journal=Integers | year=2011 | volume=11a | page=A7 | url=http://math.colgate.edu/~integers/vol11a.html | mr=2988067 | access-date=2022-10-29 | archive-date=2022-01-23 | archive-url=https://web.archive.org/web/20220123115708/http://math.colgate.edu/~integers/vol11a.html | dead-url=no }}</ref>，任兩個斐氏數之比亦不能是完全數<ref name="LucaMH2010">{{cite journal | first1=Florian | last1=Luca | first2= V. Janitzio | last2=Mejía Huguet | title=On Perfect numbers which are ratios of two Fibonacci numbers | journal=Annales Mathematicae at Informaticae | year=2010 | volume=37 | pages=107–24 | url=http://ami.ektf.hu/index.php?vol=37 | mr=2753031 | issn=1787-6117 }}</ref>。

=== 模''n''的週期性 ===
{{Main|皮萨诺周期}}

斐波那契數列各項模<math>n</math>的餘數構成{{le|週期數列|periodic sequence}}，其最小正週期稱為[[皮萨诺周期]]<ref>{{Cite OEIS|1=A001175}}</ref>，至多為<math>6n</math><ref>{{cite journal| title = Problems and Solutions: Solutions: E3410 | last1 = Freyd | first1 = Peter | last2 = Brown | first2 = Kevin S. | journal = The American Mathematical Monthly | volume = 99 | issue = 3 | pages = 278–79 |date= 1993 | doi=10.2307/2325076| jstor = 2325076 }}</ref>。皮薩諾週期對不同<math>n</math>值的通項公式仍是未解問題，其中一步需要求出某個整數（同餘意義下）或二次[[有限域]]元素的{{link-en|乘法階數|multiplicative order}}。不過，對固定的<math>n</math>，求解模<math>n</math>的皮薩諾週期是{{link-en|週期檢測|cycle detection}}<!-- 清华大学出版社1995《新英汉计算机词典》-->問題的特例。

==推廣==
斐波那西數列是[[斐波那西n步數列]]步數為2的特殊情況，也和[[盧卡斯數]]列有關。
===和盧卡斯數列的關係===
:<math>F_nL_n=F_{2n}</math>
===反費波那西數列===
反費波那西數列的遞歸公式如下：
:<math>G_{n+2} = G_{n} - G_{n+1}</math>

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

即是<math>F_{2n+1} = G_{2n+1}=F_{-(2n+1)}, F_{2n} = - G_{2n}=-F_{-2n}</math>，

亦可寫成<math>F_m = (-1)^{m+1}G_m=(-1)^{m+1}F_{-m}</math>，其中<math>m</math>是非負整數。

反費波那西數列兩項之間的比會趨近<math>-\frac{1}{\varphi} \approx -0.618</math>。
====證明關係式====
證明<math>F_m = (-1)^{m+1}F_{-m}</math>，其中<math>m</math>是非負整數
:以<math>\varphi</math>表示[[黃金分割數]]<math>\frac{1+\sqrt{5}}{2}</math>，則有<math>\varphi (1-\varphi)=-1</math>
:故<math>(-1)^m=[\varphi (1-\varphi)]^m=\varphi^m (1-\varphi)^m</math>，因此
:<math>
\begin{align}
(-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{align}
</math>

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

===佩爾數列===

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

==應用==
1970年，[[尤裏·馬季亞謝維奇]]指出了偶角標的斐波那契函數
:<math> y = F_{2x}</math>
正是滿足Julia Robison假設的[[丟番圖函數]]，因而證明了[[希爾伯特第十問題]]是不可解的。

=== 電腦科學 ===
[[File:Fibonacci Tree 6.svg|thumb|right|360px|高為6的斐波那契樹。[[AVL树|平衡因子]]以綠色標記，節點的高度則為紅色。<p>最左一條路徑上的鍵值全為斐氏數。</p>]]
*考慮以[[輾轉相除法]]求兩個正整數的[[最大公因數]]，分析此算法的[[算法分析|運行時間]]。同等輸入規模下，最壞情況（用時最長）發生於輸入為兩個相鄰斐氏數時。<ref>{{cite book| first= Donald E |last= Knuth| author-link= Donald Knuth | year =1997|title=The Art of Computer Programming | volume = 1: Fundamental Algorithms|edition= 3rd | publisher = Addison–Wesley |isbn=978-0-201-89683-1 | page = 343}}</ref>
*[[归并排序]]算法有一多相（{{lang|en|polyphase}}）版本用到斐氏數列，是將未排序的數組分為兩份，長度為相鄰的斐氏數（因此比值接近黃金比）。《[[计算机程序设计艺术]]》{{頁碼請求}}描述了此種{{link-en|多相合併排序|polyphase merge sort}}<!--https://terms.naer.edu.tw/detail/3fe1de168a2f070fd6ad111e19d90c80/ -->的實作方法，適用於以[[磁带机]]為外存的情況。
*{{anchor|斐波那契樹}}斐波那契樹是一棵[[二叉树]]，其每個節點的左右子[[树高]]皆恰好差1。由此，斐氏樹為[[AVL树]]，且對固定高度而言，是最少節點的AVL樹。此類樹的節點數可寫成斐氏數減1。<ref>{{cite journal|last1=Adelson-Velsky|first1=Georgy|last2=Landis|first2=Evgenii|year=1962|title=An algorithm for the organization of information|journal={{link-en|Proceedings of the USSR Academy of Sciences}}|volume=146|pages=263–266|language=ru}} Myron J. Ricci 的[https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf 英文翻譯] {{Wayback|url=https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf |date=20210308152754 }}載於 ''Soviet Mathematics - Doklady'', 3:1259–1263, 1962.</ref>
* 某些[[伪随机数生成器]]用到斐氏數列。{{如何？}}<!-- Knuth vol. 2 -->
* [[斐波那契堆]]是一種數據結構，分析其[[時間複雜度]]時會用到斐波那契數。
*[[斐波那契编码]]是以01字串表示正整數的一種方法，{{link-en|負斐波那契編碼|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皮科夫.數學之戀.湖南科技出版社.

== 參考文獻 ==
{{reflist|30em}}
* {{cite book | last = Livio | first = Mario | author-link = Mario Livio | title = The Golden Ratio: The Story of Phi, the World's Most Astonishing Number | url = https://books.google.com/books?id=bUARfgWRH14C | orig-year = 2002 | edition = First trade paperback | year = 2003 | publisher = [[Random House|Broadway Books]] | location = New York City | isbn = 0-7679-0816-3 | ref = harv | access-date = 2022-10-30 | archive-date = 2023-03-13 | archive-url = https://web.archive.org/web/20230313121951/https://books.google.com/books?id=bUARfgWRH14C | dead-url = no }}

== 註釋 ==
{{NoteFoot}}

==參見==
*[[齊肯多夫定理]]

==外部連結==
*[https://web.archive.org/web/20070508175938/http://www.hytc.cn/xsjl/szh/lec5.pdf 費波那契數，孫智宏（pdf）]
* [http://www.mathpages.com/home/kmath078/kmath078.htm Periods of Fibonacci Sequences Mod m] at MathPages
* [http://www.physorg.com/news97227410.html Scientists find clues to the formation of Fibonacci spirals in nature] {{Wayback|url=http://www.physorg.com/news97227410.html |date=20090209121913 }}
* {{In Our Time|Fibonacci Sequence|b008ct2j|Fibonacci_Sequence}}
* {{springer|title=Fibonacci numbers|id=p/f040020}}

{{級數}}
{{貴金屬比例}}
{{Authority control}}

[[Category:整數數列|Fibonacci]]
[[Category:斐波那契数| ]]