這篇筆記主要會整理如何對費波那契數列(Fibonacci Sequence)的遞迴式進行數學運算，並將其轉換為可以項數索引值表示的一般式結構。

What’s Fibonacci Sequence?

首先簡單定義著名的費波那契數列遞迴式:

滿足$F_1=F_2=1$且$\forall n∈N$存在以下關係:

$F_{n+2} = F_n + F_{n+1}$

則將此序列稱為費波那契數列(Fibonacci Sequence)。

因此我們可以透過以上的等式列出此數列的前幾項:
$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…$

History of Fibonacci Sequence

公元 1150 年，印度數學家 Gopala 在研究箱子包裝物件長寬剛好為 1 和 2 的可行方法數目時，首先描述這個數列。而接著在歐洲的義大利數學家費波那契(Fibonacci)則在描述兔群生長問題時，使用了這個數列來描述之，費波那契數列也因此開始受到廣泛的研究。

該問題細部如下:

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

這項問題的每個月存在兔子對數即構成費波那契數列。

費波那契數列的應用十分廣泛，包括黃金比例、植物學的葉形分布、以及許多的數學性質、最佳化理論等，對於這項數列都有著十分神奇的關聯性，事實上數學家廣泛認為這與費波那契數列的黃金比例性質有關。

Thinking

在將費波那契數列轉換為一般式之前，我們先來複習高中所學到的遞迴式轉換為一般式的過程。

Example 1 (一階遞迴)

已知數列${a_n}$的首項$a_1=1$，且該數列滿足$a_{n+1}=a_{n}\times \dfrac{n}{n+1}$，$\forall n \in N$，求$a_n$的一般式$?$

Solution:
$a_2=a_1\times \dfrac{1}{2}$
$a_3=a_2\times \dfrac{2}{3}$
$a_4=a_3\times \dfrac{3}{4}$
$…$
$\times)a_n=a_{n-1}\times \dfrac{n-1}{n}$
$———————————–$
$a_n=a_1\times \dfrac{1}{n}$

又$a_1=1$
$\implies a_n=\dfrac{1}{n}，\forall n \in N$

Example 1運用了累乘法來對遞迴式進行處理，這類對遞迴式進行四則運算的手法經常被運用到解決單純一階遞迴一般式的問題利用遞迴項恆等式的四則運算來消去不必要的項目，獲得最終以$n$表示的一般項。也許你會問，遞迴式化簡真的如此簡單嗎?讓我們看看另一個例子。

Example 2 (二階遞迴)

$a_1=1，a_2=1，a_{n+2}=2a_{n+1}+3a_n，n \in N$，求$a_n$的一般式$?$

Solution:
將原遞迴式利用未知數$k$移項一下，可得

$a_{n+2}=2a_{n+1}+3a_n\implies a_{n+2}-ka_{n+1}=(2-k)a_{n+1}+3a_n$

需求適當$k$使得遞迴式左右皆呈單項，列式可得$\dfrac{1}{2-k}=\dfrac{-k}{3}$
解方程式得$k=-1$ $or$ $3$。

① $k=-1$

代回原遞迴式得$a_{n+2}+a_{n+1}=3(a_{n+1}+a_n)=3^2(a_n+a_{n-1})=$ $…$
$=3^n(a_2+a_1)=2\cdot 3^n$

② $k=3$

代回原遞迴式得$a_{n+2}-3a_{n+1}=(-1)(a_{n+1}-3a_n)=(-1)^2(a_n-3a_{n-1})=$ $…$
$=(-1)^n(a_2-3a_1)=(-2)\cdot (-1)^n$

利用以上兩個結果解聯立方程式

$
\begin{cases}
a_{n+2}+a_{n+1}=2\cdot 3^n \\
a_{n+2}-3a_{n+1}=(-2)\cdot (-1)^n
\end{cases}
$

可得$a_{n+1}=\dfrac{3^n+(-1)^n}{2}$，代入$n=0$發現$a_1$符合一般式規則，即可求得一般式為

$a_n=\dfrac{3^{n-1}+(-1)^{n-1}}{2}，\forall n \in N$

上面Example 2提到了一個巧妙的變換手法，我們稱此方法為階差法，但費波那契數列是否能夠用類似的手法來處理呢?

答案是可以的。費波那契數列事實上是二階遞迴的一種，因此可以利用上方舉例的Example 2手法來處理，但因為算式的處理難易度考量，處理的手法可能會有些許的不同。此外，二階遞迴的化簡方法亦不僅一種，以下將會介紹除了階差法在內的三種方式來化簡之，一起來看看~

階差法

Method 1

根據費波那契數列遞迴式利用未知數$\alpha$移項，可得

$F_{n+2}=F_{n+1}+F_n\implies F_{n+2}-\alpha F_{n+1}=(1-\alpha)F_{n+1}+F_n$

我們使用階差法的目標在於使兩邊成為單項，因此可得等式$\dfrac{1}{1-\alpha}=\dfrac{-\alpha}{1}$

解得$\alpha =\dfrac{1\pm \sqrt{5}}{2}$

接著分別使用兩個$\alpha$的實根代回原遞迴式並解聯立方程式(可參考上方Example 2)，即可得到一般式。

但這個方法太早牽涉到根號的運算，因此解的過程會非常辛苦…😵
讓我們來看看另一種較為簡單的階差法處理方式吧!

Method 2

我們同樣利用未知數$\alpha$來對遞迴式移項，但形式有些不同:
$F_{n+2}=F_{n+1}+F_n\implies F_{n+2}-\alpha F_{n+1}=(1-\alpha)(F_{n+1}-\alpha F_n)$

接著代入索引值:

$\begin{cases}
F_{n}-\alpha F_{n-1}=(1-\alpha)(F_{n-1}-\alpha F_{n-2}) \to (1)式 \\
F_{n-1}-\alpha F_{n-2}=(1-\alpha)(F_{n-2}-\alpha F_{n-3}) \to (2)式 \\
… \\
F_4-\alpha F_3=(1-\alpha)(F_3-\alpha F_2) \to (n-3)式 \\
F_3-\alpha F_2=(1-\alpha)(F_2-\alpha F_1) \to (n-2)式
\end{cases}$

此時考慮$(1)$式$+(1-\alpha)\times(2)$式$+(1-\alpha)^2 \times(3)$式$+…+(1-\alpha)^{(n-3)}\times(n-2)$式，可得

$F_n-\alpha F_{n-1}=(1-\alpha)^{n-2}(F_2-\alpha F_1)$

再代入一次索引值:

$\begin{cases}
F_n-\alpha F_{n-1}=(1-\alpha)^{n-2}(F_2-\alpha F_1) \to (1)式 \\
F_{n-1}-\alpha F_{n-2}=(1-\alpha)^{n-3}(F_2-\alpha F_1) \to (2)式 \\
… \\
F_4-\alpha F_3=(1-\alpha)^{2}(F_2-\alpha F_1) \to (n-3)式 \\
F_3-\alpha F_2=(1-\alpha)(F_2-\alpha F_1) \to (n-2)式
\end{cases}$

此時接著考慮$(1)$式$+\alpha\times(2)$式$+\alpha^2 \times(3)$式$+…+\alpha^{(n-3)}\times(n-2)$式，可得等式
$F_n-\alpha^{n-2}F_2=(F_2-\alpha F_1)(1-\alpha)^{n-2}\cdot\dfrac{(1-(\dfrac{\alpha}{1-\alpha})^{n-2})}{1-\dfrac{\alpha}{1-\alpha}}$

以$F_1=F_2=1$代回求得$F_n=\dfrac{(1-\alpha)^n-\alpha^n}{1-2\alpha}$

最後一步就是將$\alpha$的值求出!

以遞迴式規則可以輕易求出$F_3=2$，將其代回上方的$(n-2)$式求解可得等式

$2-\alpha=(1-\alpha)^2\implies \alpha^2-\alpha-1=0$

解得$\alpha=\dfrac{1\pm \sqrt{5}}{2}$，代回原式!

求得費波那契數列一般項$F_n=\dfrac{1}{\sqrt{5}}((\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n)$

現在知道為什麼費氏數列的一般項化簡會這麼麻煩了嗎~:P

矩陣法

上面的階差法運用了類似於等比數列的概念將費波那契數列轉換為一般項，因此若運用類似的方法，推測矩陣應亦能達成此效果。以下為推導過程:

利用觀察法，可以將費氏數列的原遞迴式改寫為矩陣形式
$F_{n+1}=F_{n}+F_{n-1}\implies \left(
\begin{array}{c}F_{n+1} \\ F_{n} \\ \end{array} \right)=\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\
\end{array} \right) \left( \begin{array}{c} F_{n} \\ F_{n-1} \\ \end{array} \right)$

繼續下推可得$\left(
\begin{array}{c}F_{n+1} \\ F_{n} \\ \end{array} \right)=\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\
\end{array} \right)^{n-1} \left( \begin{array}{c} F_{2} \\ F_{1} \\ \end{array} \right)$

故我們只要將$\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \\
\end{array} \right)^{n-1}$求出即可獲得一般式。而因為此法為求矩陣高次方，故直接利用對角化性質求解。

令原矩陣之特徵值(Eigenvalue)為$\lambda$，特徵向量為$x$，矩陣$A=\left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \\
\end{array} \right)$，需求解$\lambda$使得$Ax=\lambda x$(特徵方程式定義)。經過移項可得$(A-\lambda I)x=0(I$是為了簡化計算而乘入，不影響計算結果$)$，根據矩陣與行列式互換性質得$det(A-\lambda I)=0\implies det\left( \begin{array}{cc} 1-\lambda & 1 \\ 1 & -\lambda \\
\end{array} \right)=0\implies \lambda^2-\lambda-1=0$，解得$\lambda=\dfrac{1\pm \sqrt{5}}{2}$，可求出其中兩個特徵向量$x=\left(\begin{array}{c} \dfrac{1\pm \sqrt{5}}{2} \\ 1 \end{array} \right)$

以此為基礎對矩陣$A$進行對角化可得

$\left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)=\left(\begin{array}{cc} \dfrac{1+\sqrt{5}}{2} & \dfrac{1-\sqrt{5}}{2} \\ 1 & 1 \end{array} \right)\left(\begin{array}{cc} \dfrac{1+\sqrt{5}}{2} & 0 \\ 0 & \dfrac{1-\sqrt{5}}{2} \end{array} \right)\dfrac{1}{\sqrt{5}}\left(\begin{array}{cc} 1 & -\dfrac{1-\sqrt{5}}{2} \\ -1 & \dfrac{1+\sqrt{5}}{2} \end{array} \right)$，故

$\left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)^{n-1}=\left(\begin{array}{cc} \dfrac{1+\sqrt{5}}{2} & \dfrac{1-\sqrt{5}}{2} \\ 1 & 1 \end{array} \right)\left(\begin{array}{cc} (\dfrac{1+\sqrt{5}}{2})^{n-1} & 0 \\ 0 & (\dfrac{1-\sqrt{5}}{2})^{n-1} \end{array} \right)\dfrac{1}{\sqrt{5}}\left(\begin{array}{cc} 1 & -\dfrac{1-\sqrt{5}}{2} \\ -1 & \dfrac{1+\sqrt{5}}{2} \end{array} \right)$

$=\dfrac{1}{\sqrt{5}}\left(\begin{array}{cc} (\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n & -\dfrac{1-\sqrt{5}}{2}(\dfrac{1+\sqrt{5}}{2})^{n}+\dfrac{1+\sqrt{5}}{2}(\dfrac{1-\sqrt{5}}{2})^{n} \\ (\dfrac{1+\sqrt{5}}{2})^{n-1}-(\dfrac{1-\sqrt{5}}{2})^{n-1} & -\dfrac{1-\sqrt{5}}{2}(\dfrac{1+\sqrt{5}}{2})^{n-1}+\dfrac{1+\sqrt{5}}{2}(\dfrac{1-\sqrt{5}}{2})^{n-1} \end{array} \right)$

將其代回原式並將矩陣乘開即可求得費波那契數列一般項$F_n=\dfrac{1}{\sqrt{5}}((\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n)$

P.S.最後一步建議不要用根與係數把$n$次多項式乘開!不然可能會因為消不掉而卡住…乘開成這樣是最好消去的狀態!(除非您是通靈電神，可以在兩個根自由互換 Orz)

我想起了被矩陣對角化支配的”美好”時光…><

生成函數法

西元 1843 年, 法國數學家棣美弗(Jacques-Philippe-Marie Binet)利用一般生成函數求出費氏數列的一般式。這是人類紀錄史上第一次求出費氏數列一般項，也是生成函數應用於數學史的拓展。

但事實上我原本並不知道這個做法，生成函數並不在高中教材中，但就應用層面而言，它的使用廣泛度事實上遠遠超乎我們的想像，舉凡我們常用的排列組合、遞迴關係等，都可以將原來的形式$(C^m_n、P^m_n、H^m_n、$遞迴式$…)$轉換為函數的形式。但要完整的介紹生成函數事實上並不容易，我對於生成函數也不算熟悉，因此在此就僅整理生成函數如何轉換費波那契數列的部分。

利用普通生成函數(OGF，ordinary generating function)冪級數$\sum\limits_{i = 0}^\infty{a_ix^i}$對費氏數列做一般數列轉換成生成函數，可將其表為$\sum\limits_{k=1}^\infty{F_kx^k}_{(註1)}$，令其為$g(x)$並展開可得:
$g(x)=F_1x+F_2x^2+F_3x^3+F_4x^4+…(1)$式
對該函數動一點手腳:
$xg(x)=F_1x^2+F_2x^3+F_3x^4+F_4x^5+…(2)$式
再來一點:
$x^2g(x)=F_1x^3+F_2x^4+F_3x^5+F_4x^6+…(3)$式

接著代入$F_1=F_2=1$，當$|x|<1$時，以$(1)$式$-(2)$式$-(3)$式可得$(1-x-x^2)g(x)=x\implies g(x)=\dfrac{x}{1-x-x^2}$

$=\dfrac{x}{(1-\dfrac{1+\sqrt{5}}{2}x)(1-\dfrac{1-\sqrt{5}}{2}x)}$

$=\dfrac{1}{\sqrt{5}x}(\dfrac{1}{\dfrac{1}{x}-\dfrac{1+\sqrt{5}}{2}}-\dfrac{1}{\dfrac{1}{x}-\dfrac{1-\sqrt{5}}{2}})…$(分項對消)

此時需引入勞倫級數(Laurent series)概念，在此不解說其深入概念，但是利用之，考慮以上部分分數展開式，可得該級數為
$g(x)=\dfrac{1}{\sqrt{5}x}\sum\limits_{n=1}^\infty{((\dfrac{1+\sqrt{5}}{2})^{n-1}-
(\dfrac{1-\sqrt{5}}{2})^{n-1})x^n}$

$=\dfrac{1}{\sqrt{5}}\sum\limits_{n=1}^\infty{((\dfrac{1+\sqrt{5}}{2})^{n-1}-
(\dfrac{1-\sqrt{5}}{2})^{n-1})x^{n-1}}$

代入後與原$g(x)$比較係數可得費波那契數列一般項$F_n=\dfrac{1}{\sqrt{5}}((\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n)$

註 1:這一步的定義事實上不夠嚴謹與詳細，詳情請見生成函數之生成方法與限制，其中牽涉到映成函數、光滑函數與完全歸納法等的運算。

Conclusion

費氏數列的神奇之處，在於其遞迴式將無理數的運算表示為有理數的遞迴式，這在數學的運算上事實上並不常見。而透過我們所推導出的一般式，我們也可以發現，費波那契數列可以被表為線性的形式$F_n=\alpha(\dfrac{1+\sqrt{5}}{2})^n+\beta(\dfrac{1-\sqrt{5}}{2})^n$，這凸顯了其之線性組合的特性，事實上，這個性質的類似方法也可以做為導出一般項的作法，一起來看看最後一種導出法吧~

Bonus : 線性置換法

這裡所謂的線性，是指在透過利用費氏數列的組合下，求得一般項的方法。首先，我們可以十分簡單地推出以下兩個費氏數列的性質:

1.$(F_i)_i，(G_i)_i$均為費氏數列，則$(F_i+G_i)_i$亦為費氏數列。

$(F_{n+2}+G_{n+2})=(F_{n+1}+F_{n})+(G_{n+1}+G_{n})=(F_{n+1}+G_{n+1})+(F_{n}+G_{n})$，即可推出。

2.承上，$(\alpha F_i)_i$亦為費氏數列

$(\alpha F_{n+2})=\alpha(F_{n+1}+F_n)=(\alpha F_{n+1})+(\alpha F_n)$，即可推出。

由上兩點可以證明費氏數列經過線性組合仍為費氏數列。

因此我們可以考慮在$a_n$與$b_n$均為費氏數列(不考慮$F_1=F_2=1$之條件)的情況下，取$\alpha、\beta$ $s.t.$ $\alpha、\beta\in R$，令新數列$H_n=\alpha a_n+\beta b_n$，則新數列$H_n$為一費氏數列。從上我們可以知道，只要取得適當之數列與代數即可。

但我們如何定義$a_n$與$b_n$的存在呢?我們首先透過我們熟悉的數列來定義之，因為其是費氏數列之子元素，這樣的取法不影響我們對於費氏數列的定義。首先，若$a_n$與$b_n$為等差數列，他是沒有辦法滿足費氏數列的性質的。因此，我們考慮等比數列。若$a_n$與$b_n$屬於等比數列，又其兩者為費氏數列，可令其中一者之一般項為$a_n=kr^{n-1}$，因此透過費氏數列定義，$kr^{n+2}=kr^{n+1}+kr^n$，設定$k\ne0，r\ne1$，則可列出算式$r^2-r-1=0$，解得$a_n、b_n=((\dfrac{1\pm\sqrt{5}}{2})^{i-1})^{\infty}_{i=1}$

此時帶回原式解$\alpha$與$\beta$，且原數列$H$須滿足費氏數列之$F_1=F_2=1$性質，由此可列出以下方程式:

$\begin{cases}
1=\alpha+\beta \\
1=\dfrac{1+\sqrt{5}}{2}\alpha+\dfrac{1-\sqrt{5}}{2}\beta
\end{cases}$

解得$\alpha=\dfrac{1}{\sqrt{5}}(\dfrac{1+\sqrt{5}}{2})、\beta=-\dfrac{1}{\sqrt{5}}(\dfrac{1-\sqrt{5}}{2})$，將四項條件代回原式即可求得費波那契數列一般項

$H_n=\dfrac{1}{\sqrt{5}}((\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n)$