斐波那契数列

跳过字词转换说明

以費波那西數為邊的正方形拼成的長方形

費波那西數列（Fibonacci Sequence），又譯費波拿契數、斐波那契數列、費氏數列、黃金分割數列。

在數學上，費波那西數列是以遞歸的方法來定義：

• F₀ = 0
• F₁ = 1
• F_n = F_{n − 1} + F_{n − 2}

用文字來說，就是費波那西數列由 0 和 1 開始，之後的費波那西係數就由之前的兩數相加。首幾個費波那西係數是（OEIS A000045）：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，………………

特別指出：0不是第一項，而是第零項。

源起

根據高德納（Donald Ervin Knuth）的《計算機程序設計藝術》（The Art of Computer Programming），1150年印度數學家Gopala和金月在研究箱子包裝物件長闊剛好為 1 和 2 的可行方法數目時，首先描述這個數列。 在西方，最先研究這個數列的人是比薩的李奧納多（又名費波那西），他描述兔子生長的數目時用上了這數列。

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

假設在 n 月有新生及可生育的兔子總共 a 對，n+1 月就總共有 b 對。在 n+2 月必定總共有 a+b 對： 因為在 n+2 月的時候，所有在 n 月就已存在的 a 對兔子皆已可以生育並誕下 a 對後代；同時在前一月(n+1月)之 b 對兔子中，在當月屬於新誕生的兔子尚不能生育。

表達式

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

初等代數解法

已知

• a₁ = 1
• a₂ = 1
• a_n = a_{n − 1} + a_{n − 2}

首先構建等比數列

設a_n + αa_{n − 1} = β(a_{n − 1} + αa_{n − 2})
化簡得
a_n = (β − α)a_{n − 1} + αβa_{n − 2}
比較係數可得:
$\begin{cases} \beta-\alpha=1 \\ \alpha\beta=1 \end{cases}$
不妨設β > 0,α > 0
解得：

$\begin{cases} \alpha=\dfrac{\sqrt{5}-1}{2} \\ \beta=\dfrac{\sqrt{5}+1}{2} \end{cases}$
所以有a_n + αa_{n − 1} = β(a_{n − 1} + αa_{n − 2})， 即$\left\{a_n +\alpha a_{n-1}\right\}$為等比數列。

求出數列{a_n + αa_{n − 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}\frac{a_{n}}{\beta^{n}}=\frac{1}{\beta}$。 令$b_n=\frac{a_n}{\beta^n}$

求數列{b_n}進而得到{a_n}

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

線性代數解法

構建一個矩陣方程

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

求矩陣的特徵值：λ

行列式：-λ*(1-λ)-1*1=λ2-λ-1

當行列式的值為0，解得λ₁=$\frac{1}{2} (1 + \sqrt{5})$ 或 λ₂=$\frac{1}{2} (1 - \sqrt{5})$

特徵向量

將兩個特徵值代入

$\begin{pmatrix}0&1\\1&1\end{pmatrix}-\lambda \cdot E) \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 [\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}]$

根據 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 ((\frac{1}{2} (1 + \sqrt{5}))^{n+1} - (\frac{1}{2} (1 - \sqrt{5}))^{n+1})$ (7)

(7)即為A_n+1 的表達式

近似值

$F_n \approx \frac{1}{\sqrt{5}} a^n = \frac{1}{\sqrt{5}} \cdot ( \frac{1}{2} (1 + \sqrt{5}) )^n \approx 0.4472135955 \cdot 1.618033988745^n$

用計算機求解

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

可通過遞歸遞推的算法解決此兩個問題。 事實上當n相當巨大的時候，O(n)的遞推/遞歸非常慢……這時候要用到矩陣加速這一技巧。

和黃金分割的關係

開普勒發現兩個斐波那契數的比會趨近黃金分割：

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

和自然的關係

許多的生物構成都和斐波那契數列有正相關。例如人體從肚臍至頭頂之距離和從肚臍至腳底之距趨近於$\lim_{n \to \infty}\frac{F_n}{F_(n-1)}$ ,向日葵的種子螺旋排列99%是F_n。

恆等式

證明以下的恆等式有很多方法。以下會用組合論述來證明。F_n可以表示成用多個1和多個2相加令其和等於<mat 不失一般性，我們假設n ≥ 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₁ + F₂ + F₃ + ... + 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₀為要求的數目。

• F₁ + 2F₂ + 3F₃ + ... + nF_n = nF_{n + 2} − F_{n + 3} + 2

• F₁ + F₃ + F₅ + ... + F_{2n − 1} = F_2n
• F₂ + F₄ + F₆ + ... + 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-1} F_{n+1} - {F_n}^2 = (-1)^n$

相關的數列

費波那西數列是費波那西n步數列步數為2的特殊情況，也和盧卡斯數列有關。

反費波那西數列

反費波那西數列的遞歸公式如下：

G_{n + 2} = G_n − G_{n + 1}

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

即是F_{2n + 1} = G_{2n + 1},F_2n = − G_2n。

反費波那西數列兩項之間的比會趨近$-\frac{1}{\varphi}=-0.618$。

巴都萬數列

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

應用

1970年，Yuri Matiyasevich 指出了偶角標的斐波那契函數

y = F_2x

正是滿足 Julia Robison 假設的丟番圖函數，因而證明了希爾伯特第十問題是不可解的。

相关猜想

斐波那契數列中是否存在無窮多個素數？

在斐波那契數列中，有素數： 2,3,5,13,89,233,1597,28657,514229,433494437,2971215073,99194853094755497,1066340417491710595814572169,19134702400093278081449423917…… 目前已知最大素數是第81839個斐波那契數，一共有17103位數。

參考

• Donald E. Knuth: THE ART OF COMPUTER PROGRAMMING Volume 1/Fundamental

Algorithms. 第一章第 1.2.8 節《斐波那契數》。

• 《数学之恋》【美】克里福德A皮科夫著，湖南科技出版社

參見

• 齊肯多夫定理

外部連結

• 費波那契數，孫智宏(pdf)
• 費氏數列
• 費波那西數列
• 費波那西數列簡介