Fibonacci数列

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

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

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

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

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

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

#### 求出數列 $\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}$ 的表達式。

#### 求矩陣的特徵值： $\lambda $

根據特徵值的計算公式，我們需要算出來 ${\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}}$

#### 求 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{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+...}}}}}}}}$

## 和自然的關係

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

## 恆等式

資料來源：

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

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

不失一般性，我們假設 $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. 若第 1 個被加數是 2，有 $F_{n}$ 種方法來計算加至 $n-1$ 的方法的數目；
2. 若第 2 個被加數是 2、第 1 個被加數是 1，有 $F_{n-1}$ 種方法來計算加至 $n-2$ 的方法的數目。
3. 重複以上動作。
4. 若第 $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$
 * $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_{n}F_{m-k}-F_{m}F_{n-k}=(-1)^{n-k}F_{m-n}F_{k}$ ，其中 $m,n,k$ 與 $F$ 的序數皆不限於正整數。
  * 特別地，當 $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_{n}F_{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$ 為任意整數

　
: : 藉由上述公式，又可推得以下恆等式：

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

## 數論性質

### 公因數和整除關係

 * $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_{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 假設的丟番圖函數，因而證明了希爾伯特第十問題是不可解的。

### 電腦科學

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

## 程式參考

JavaScript 迭代版

C 語言通項公式版

c++ 二變數求某項版

c++ 通項公式版

Python 語言通項公式版

Common Lisp

Go

遞迴版，時間複雜度為 O (2^n)：

通用版，時間複雜度為 O (n)：

Java 語言遞迴版：

Java 語言快捷版：

C 語言陣列版：

Python Lambda 遞迴版:

## 延伸閱讀

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

## 參考文獻

* 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]. ISBN 0-7679-0816-3.

## 註釋

## 參見

* 齊肯多夫定理

## 外部連結

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