zh.wikipedia.org

斐波那契数 - 维基百科，自由的百科全书

️Sat Jan 04 2014

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

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

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

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

特別指出：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\}$ 為等比數列。

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

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

[编辑]

$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}$ 的表達式。

根据特征值的计算公式，我们需要算出来 ${\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}}$

現在在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}}$ ^[1]

$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$ 為任意整數^{[註 1]}，則

${\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)。

開普勒發現數列前、後兩項之比 ${\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（淺藍）條旋臂，為相鄰的斐氏數。類似的螺旋狀排列見於多種植物。

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

資料來源：^[11]

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

不失一般性，我們假設 $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個被加數是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}+2F_{2}+3F_{3}+...+nF_{n}=nF_{n+2}-F_{n+3}+2$

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

$\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]

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

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

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

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

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

斐波那契數列各項模 $n$ 的餘數構成週期數列，其最小正週期稱為皮萨诺周期^[23]，至多為 $6n$ ^[24]。皮薩諾週期對不同 $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假設的丟番圖函數，因而證明了希爾伯特第十問題是不可解的。

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

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

^ 斐波那契数列与组合数的一个关系及推广. [2014-01-04]. （原始内容存档于2019-05-02）.
^ 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）.
^ Jones, Judy; Wilson, William. Science. An Incomplete Education. Ballantine Books. 2006: 544. ISBN 978-0-7394-7582-9.
^ Brousseau, A. Fibonacci Statistics in Conifers. Fibonacci Quarterly. 1969, (7): 525–32.
^ Marks for the da Vinci Code: B–, Maths (Computer Science For Fun: CS4FN), [2022-10-30], （原始内容存档于2009-05-31）
^ 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）
^ Livio 2003，第110頁.
^ Livio 2003，第112–13頁.
^ Varenne, Franck. Formaliser le vivant - Lois, Théories, Modèles. Hermann. 2010-11-16: 28 [2022-10-30]. ISBN 9782705678128. （原始内容存档于2022-10-30）.
^ The Secret of the Fibonacci Sequence in Trees. 美國自然史博物館. 2011 [2019-02-04]. （原始内容存档于2013-05-04）.
^ ^11.0 ^11.1 ^11.2 李晨滔、馮勁敏. 費氏數列的性質整理 (PDF). 桃園縣立大園國際高中. [2018-01-28]. （原始内容存档 (PDF)于2019-06-25）.
^ Sloane, N.J.A. (编). Sequence A005478. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Weisstein, Eric W. (编). Fibonacci Prime. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）.
^ Honsberger, Ross. Mathematical Gems III. AMS Dolciani Mathematical Expositions. 1985, (9): 133. ISBN 978-0-88385-318-4.
^ 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.
^ 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
^ Pethő, Attila. Diophantine properties of linear recursive sequences II. Acta Mathematica Academiae Paedagogicae Nyíregyháziensis. 2001, 17: 81–96. MR 1887650.
^ 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.
^ Luo, Ming. On triangular Fibonacci numbers (PDF). Fibonacci Quart. 1989, 27 (2): 98–108 [2022-10-29]. MR 0995557. （原始内容存档 (PDF)于2022-10-29）.
^ 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.
^ 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）.
^ 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.
^ Sloane, N.J.A. (编). Sequence A001175. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ 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.
^ Knuth, Donald E. The Art of Computer Programming. 1: Fundamental Algorithms 3rd. Addison–Wesley. 1997: 343. ISBN 978-0-201-89683-1.
^ Adelson-Velsky, Georgy; Landis, Evgenii. An algorithm for the organization of information. 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）.

齊肯多夫定理

費波那契數，孫智宏（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

斐波那契数 - 维基百科，自由的百科全书

求數列進而得到

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