費布納西數列的表達式

本文的閱讀等級:初級

公元十三世紀義大利數學家費布納西 (Leonardo Pisano Bigollo,又名 Leonardo Fibonacci) 在研究兔群生長的問題時發明了一種無窮數列:第0項為0,第1項為1,以後的各項等於之前兩項的和。後人稱它為費布納西數列,下面列出最初幾項:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…

費布納西數列和許多自然界現象的數學結構有密切關係。大多數植物的花瓣數目都屬於費布納西數 (費布納西數列的各項)。大型向日葵頭上的小花 (floret) 排列成兩組交錯螺線,一組順時針旋轉,另一組逆時針旋轉。兩組螺線確切的數目由品種決定,但通常是兩相鄰的費布納西數[1],譬如,34與55,或55與89[維基百科圖例]。不僅如此,兩相鄰費布納西數的比趨於黃金比例:

\displaystyle\phi=\frac{1+\sqrt{5}}{2}\approx 1.6180339887\ldots

例如,55/34=1.6176470588…,89/55=1.6181818181…。西方人著迷黃金比例已有超過二千年的歷史[2],費布納西數列與黃金比例的特殊關係更因此讓它蒙上一層神秘色彩。由於上述種種原因,費布納西數列經常出現於大眾文化中,如電影、文學、視覺藝術,甚至音樂[3]。本文要討論的是一個單純的數學問題:推導費布納西數列的一般表達式。

 
F_k 代表費布納西數列的第 k 項。費布納西數列的遞歸生成規則可用差分方程表示為

F_{k+2}=F_{k+1}+F_{k},~~k=0,1,2,\ldots

並給定初始條件 F_0=0F_1=1。運用中學初等代數即可求出 F_k[4],下面我介紹線性代數解法。首先,將二階差分方程改為矩陣表述。引入一恆等式,如下:

\begin{aligned} F_{k+2}&=F_{k+1}+F_k\\ F_{k+1}&=F_{k+1},\end{aligned}

再以矩陣表示為

\begin{bmatrix} F_{k+2}\\  F_{k+1}  \end{bmatrix}=\begin{bmatrix}  1&1\\  1&0  \end{bmatrix}\begin{bmatrix} F_{k+1}\\ F_k \end{bmatrix}

\mathbf{u}_k=\begin{bmatrix} F_{k+1}\\  F_k  \end{bmatrix},即得差分方程標準式:

\mathbf{u}_{k+1}=A\mathbf{u}_k,~~k=0,1,\ldots

其中 A=\begin{bmatrix}  1&1\\  1&0  \end{bmatrix},初始條件為 \mathbf{u}_0=\begin{bmatrix}  1\\  0  \end{bmatrix}

 
解差分方程等同於計算冪矩陣 A^k,因為

\mathbf{u}_k=A\mathbf{u}_{k-1}=A(A\mathbf{u}_{k-2})=A^2\mathbf{u}_{k-2}=\cdots=A^k\mathbf{u}_0

只要算出 A^k,令之與初始向量 \mathbf{u}_0 相乘即得 \mathbf{u}_k。當 n\times n 階矩陣 A 是可對角化時 (若 A 不可對角化,請見“利用 Jordan form 解差分方程與微分方程”),A^k 的計算工作變得十分簡單。設 A=S\Lambda S^{-1},其中 \Lambda=\mathrm{diag}(\lambda_1,\ldots,\lambda_n)\lambda_1,\ldots,\lambda_nA 的特徵值,可逆矩陣 S 的行向量 (column vector) 由對應的特徵向量 \mathbf{x}_1,\ldots,\mathbf{x}_n 組成。因為 A^k=S\Lambda^kS^{-1},於是有下列簡化形式:

\mathbf{u}_k=S\Lambda^kS^{-1}\mathbf{u}_0

此外,我們還可以將 \mathbf{u}_k 表示成特徵向量 \mathbf{x}_1,\ldots,\mathbf{x}_n 的線性組合。令 \mathbf{c}=S^{-1}\mathbf{u}_0,展開矩陣乘法可得通解,如下:

\begin{aligned}  \mathbf{u}_k&=S\Lambda^k\mathbf{c}\\  &=\begin{bmatrix}  \mathbf{x}_1&\cdots&\mathbf{x}_n  \end{bmatrix}\begin{bmatrix}  \lambda_1^k&~&~\\  ~&\ddots&~\\  ~&~&\lambda_n^k  \end{bmatrix}\begin{bmatrix}  c_1\\  \vdots\\  c_n  \end{bmatrix}\\ &=\begin{bmatrix} \lambda_1^k\mathbf{x}_1&\cdots&\lambda_n^k\mathbf{x}_n \end{bmatrix}\begin{bmatrix} c_1\\ \vdots\\ c_n \end{bmatrix}\\ &=c_1\lambda_1^k\mathbf{x}_1+\cdots+c_n\lambda_n^k\mathbf{x}_n,\end{aligned}

k=0,上式便為 \mathbf{u}_0=S\Lambda^0\mathbf{c}=SI\mathbf{c}=S\mathbf{c},解出係數 c_1,\ldots,c_n 即大功告成。

 
以下是費布納西數列表達式的詳細推導過程。

步驟一:解出特徵值與特徵向量。

寫出方陣 A 的特徵多項式:

p(\lambda)=\det(A-\lambda I)=\begin{vmatrix}  1-\lambda&1\\  1&-\lambda  \end{vmatrix}=\lambda^2-\lambda-1

可得兩共軛根:

\displaystyle\lambda_1=\frac{1+\sqrt{5}}{2},~\lambda_2=\frac{1-\sqrt{5}}{2}

觀察出 \lambda_1+\lambda_2=1\lambda_1\lambda_2=-1。接著計算零空間 N(A-\lambda_1I)N(A-\lambda_2I) 的基底,此即對應的特徵向量:

\mathbf{x}_1=\begin{bmatrix}  \lambda_1\\  1  \end{bmatrix},~\mathbf{x}_2=\begin{bmatrix}  \lambda_2\\  1  \end{bmatrix}

於是有通解:

\mathbf{u}_k=c_1\lambda_1^k\mathbf{x}_1+c_2\lambda_2^k\mathbf{x}_2

步驟二:使用初始條件計算組合係數。

k=0,代入初始條件 \mathbf{u}_0

\begin{bmatrix}  1\\  0  \end{bmatrix}=c_1\begin{bmatrix}  (1+\sqrt{5})/2\\  1  \end{bmatrix}+c_2\begin{bmatrix}  (1-\sqrt{5})/2\\  1  \end{bmatrix}

由此解出 c_1=1/\sqrt{5}c_2=-1/\sqrt{5},故得

\displaystyle  \mathbf{u}_k=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^k\begin{bmatrix}  (1+\sqrt{5})/2\\  1  \end{bmatrix}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^k\begin{bmatrix}  (1-\sqrt{5})/2\\  1  \end{bmatrix}

費布納西數列的表達式即為 \mathbf{u}_k 的第二個元:

\displaystyle  F_k=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^k-\left(\frac{1-\sqrt{5}}{2}\right)^k\right],~~k=0,1,2,\ldots

 
從費布納西數列的表達式可推演出下列性質。

(1) 當 k 增大時,第二項 \left(\frac{1-\sqrt{5}}{2}\right)^k 迅速趨於0,因此

\displaystyle F_k\approx \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^k

並可驗證兩相鄰費布納西數的比趨於黃金比例:

\displaystyle  \frac{F_{k+1}}{F_k}\approx\frac{1+\sqrt{5}}{2}

(2) 冪矩陣 A^k 可用費布納西數表示為

A^k=\begin{bmatrix} F_{k+1}&F_k\\ F_k&F_{k-1} \end{bmatrix}

計算 A^k\begin{bmatrix} 1\\ 0 \end{bmatrix} 可得 A^k 的第一行,此即 \mathbf{u}_k。計算 A^k\begin{bmatrix} 0\\ 1 \end{bmatrix} 可得 A^k 的第二行,如下:

A^k\begin{bmatrix} 0\\ 1 \end{bmatrix}=A^{k-1}\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}\begin{bmatrix} 0\\ 1 \end{bmatrix}=A^{k-1}\begin{bmatrix} 1\\ 0 \end{bmatrix}=\mathbf{u}_{k-1}

(3) 由 (2),\det A^k=(\det A)^k=\begin{vmatrix} 1&1\\ 1&0 \end{vmatrix}^k=(-1)^k,就得到 Cassini 恆等式:

(-1)^k=F_{k+1}F_{k-1}-F_k^2

 
參考來源:
[1] Wikipedia:Fibonacci number
[2] Wikipedia:Golden ratio
[3] Wikipedia:Fibonacci numbers in popular culture
[4] 維基百科:費氏數列

相關閱讀:
This entry was posted in 特徵分析, 線性代數專欄 and tagged , , , , , . Bookmark the permalink.

5 則回應給 費布納西數列的表達式

  1. Watt Lin 說:

    老師:您的數列,是不是需要再添加一個1?
    0,1,2,3,5,8 ….
    修改為以下
    0,1,1,2,3,5,8 ….

  2. Watt Lin 說:

    老師修改的速度真快!

  3. shawn toh 說:

    好深好深好深好深的数学。。。。。。

  4. 費伯那西與向日癸 說:

    Good

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s