斐波那契數

費波那契數（義大利語：Numero di Fibonacci），又譯為菲波拿契數、菲波那西數、斐氏數、黃金分割數、費氏數列。所形成的數列稱為費波那契數列（義大利語：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），他描述兔子生長的數目時用上了這數列：

<image>

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

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

<image>

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

## 表達式

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

### 初等代數解法

已知：

- $$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} <pre> -\lambda & 1 \\ 1 & 1 - \lambda \\ </pre> \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} <pre> \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+...}}}}$$

## 和自然的關係

<image>

斐氏數列見於不同的生物學現象，如樹的分枝、葉序、菠蘿聚花果上小單果的排列、雅枝竹的花蕾、正在舒展的蕨葉、松毬的鱗的排列、蜜蜂的家族樹。克卜勒曾指出斐氏數列存在於自然界，並以此解釋某些花的五邊形形態（與黃金分割率相關）。法國菊的「瓣」（舌狀花）數通常為斐氏數。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$的序數皆不限於正整數。例如當$(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$為任意整數這可以透過$\varphi^2=1+\varphi$與$\frac{1}{\varphi}=\varphi-1$與$\frac{1}{1-\varphi}=-\varphi$此三個等式，以及費氏數列的遞歸定義，以數學歸納法證明。

藉由上述公式，又可推得以下恆等式利用指數律$\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}$
- $F_{m} F_{n+1} + F_{m-1} F_n = F_{m+n}$特別地，當$m=n$時，$\begin{align} <pre> 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 </pre> \end{align}$

## 數論性質

### 公因數和整除關係

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

$$\mathrm{gcd}(F_n, F_{n+1})=\mathrm{gcd}(F_n, F_{n+2})=\mathrm{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_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假設的丟番圖函數，因而證明了希爾伯特第十問題是不可解的。

### 電腦科學

<image>

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

## 延伸閱讀

- KNUTH, D. E. 1997. The Art 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皮科夫.數學之戀.湖南科技出版社.

## 外部連結

- 費波那契數，孫智宏（pdf）
- Periods of Fibonacci Sequences Mod m at MathPages
- Scientists find clues to the formation of Fibonacci spirals in nature
- Fibonacci Sequence