斐波那契数

(1:1.618)]]

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

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

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

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

特別指出：0 不是第一項，而是第零項（F_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\}為等比數列。

求出數列{an+αan-1}
由以上可得：

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

變形得：
\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}

求數列{bn}進而得到{an}
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}表達式
，稱(Binet's Formula)

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{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}

:亦成立
*若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{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}

:亦成立

因此，根據數學歸納法原理，此表達式對於任意整數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}

稱為「斐波那契Q矩陣」(Fibonacci Q-Matrix)
構建一個矩陣方程
設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}的表達式。

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

展开行列式有：-\lambda(1-\lambda)-1\times1=\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{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}

因此得到F_n的一般式：

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

此一般式對任意整數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)。

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

:\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+...}}}}

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

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

恆等式
資料來源：

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

F_n可以表示用多個1和多個2相加令其和等於n的方法的數目。

不失一般性，我們假設n\geq1，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個被加數是2，有F_n種方法來計算加至n-1的方法的數目；
#若第2個被加數是2、第1個被加數是1，有F_{n-1}種方法來計算加至n-2的方法的數目。
#重複以上動作。
#若第n+1個被加數為2，它之前的被加數均為1，就有F_{0}種方法來計算加至0的數目。

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

*F_1 + 2 F_2 + 3 F_3 + ... + n F_n = n F_{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_1}^3 + {F_2}^3 + {F_3}^3 + \cdots + {F_n}^3 = \frac{3F_{n+1}^2F_n-F_{n+1}^3-F_n^3+1}{2}
*F_1F_2+F_2F_3+F_3F_4+ \cdots +F_{2n}F_{2n+1}={F_{2n+1}}^2-1
*F_1F_2+F_2F_3+F_3F_4+ \cdots +F_{2n+1}F_{2n+2}={F_{2n+2}}^2
*F_nF_{m-k}-F_mF_{n-k}=(-1)^{n-k}F_{m-n}F_k，其中m,n,k與F的序數皆不限於正整數。{{NoteTag|例如當(m,n,k)=(4,-8,6)時，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}}
**特別地，當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_nF_{n+3}-F_{n+1}F_{n+2}=(-1)^{n+1}
*\varphi^n=F_{n-1}+\varphi F_n且(1-\varphi)^n=F_{n+1}-\varphi F_n，其中\varphi為黃金比例\frac{1+\sqrt{5}}{2}，n為任意整數{{NoteTag|name=varphi|1=這可以透過\varphi^2=1+\varphi與\frac{1}{\varphi}=\varphi-1與\frac{1}{1-\varphi}=-\varphi此三個等式，以及費氏數列的遞歸定義，以數學歸納法證明。}}
::藉由上述公式，又可推得以下恆等式{{NoteTag|利用指數律\varphi^{m+n}=\varphi^m \times \varphi^n、性質\varphi^2=1+\varphi，以及「若a,b,c,d是有理數，x是無理數，且滿足a+bx=c+dx，則a=c,b=d」證明。}}：
**{F_m}{F_n} + {F_{m-1}}{F_{n-1}} = F_{m+n-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為僅有的斐氏三角形數。曾猜想此結論，後來由罗明證明。

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

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

推廣
斐波那西數列是斐波那西n步數列步數為2的特殊情況，也和盧卡斯數列有關。
和盧卡斯數列的關係
:F_nL_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{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}

巴都萬數列
費波那西數列可以用一個接一個的正方形來表現，巴都萬數列則是用一個接一個的等邊三角形來表現，它有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假設的丟番圖函數，因而證明了希爾伯特第十問題是不可解的。

電腦科學
以綠色標記，節點的高度則為紅色。最左一條路徑上的鍵值全為斐氏數。
]]
*考慮以輾轉相除法求兩個正整數的最大公因數，分析此算法的運行時間。同等輸入規模下，最壞情況（用時最長）發生於輸入為兩個相鄰斐氏數時。
*归并排序算法有一多相（）版本用到斐氏數列，是將未排序的數組分為兩份，長度為相鄰的斐氏數（因此比值接近黃金比）。《计算机程序设计艺术》描述了此種的實作方法，適用於以磁带机為外存的情況。
*斐波那契樹是一棵二叉树，其每個節點的左右子树高皆恰好差1。由此，斐氏樹為AVL树，且對固定高度而言，是最少節點的AVL樹。此類樹的節點數可寫成斐氏數減1。

某些伪随机数生成器用到斐氏數列。
斐波那契堆是一種數據結構，分析其時間複雜度時會用到斐波那契數。

*斐波那契编码是以01字串表示正整數的一種方法，與之類似，還可以表示負數。

评论 (0)