費氏數列 - 矩陣推導篇

此篇數學式使用MathJax表示，請開啟瀏覽器對Java的支援。

　　接觸數列時，老師應該都會提到一組特別的數列1, 1, 2, 3, 5, 8, 13, 21, ...，這就是有名的費波那契數列，或簡稱為費氏數列，規則是後項是前兩項之和，數學式表達為
$$\left\{ \begin{array}{ll} F_{1} = 1, F_{2} = 1 \\ F_{n} = F_{(n - 1)} + F_{(n - 2)}, & n = 3, 4, 5, ... \end{array} \right.$$
或是由第0項開始描述：
$$\left\{ \begin{array}{ll} F_{0} = 0, F_{1} = 1 \\ F_{n} = F_{(n - 1)} + F_{(n - 2)}, & n = 2, 3, 4, ... \end{array} \right.$$
　　了解規則後，不僅會依序算出費氏數列，還想要推導數列的函數$F_{n} = ?$，開門見山，先給出解答，費氏函數長這樣：
$$F_{n} = \frac{\sqrt{5}}{5} \biggl[ \biggl( \frac{1 + \sqrt{5}}{2} \biggr) ^{n} - \biggl( \frac{1 - \sqrt{5}}{2} \biggr) ^{n} \biggr]$$
　　一個簡單加法，為什麼搞個那麼複雜的函數？又是根號又是$n$次方的！是怎麼推導出來的呢？接下來，就是本篇的重點，利用矩陣的方式證明費氏函數。首先把聯立的數學式改寫成矩陣形式：
$$\left[ \begin{array}{cc} F_{n} \\ F_{n - 1} \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] \left[ \begin{array}{cc} F_{n - 1} \\ F_{n - 2} \end{array} \right], \qquad n = 2, 3, 4, ...$$
若$n = 2$，則 $$\left[ \begin{array}{cc} F_{2} \\ F_{1} \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] \left[ \begin{array}{cc} F_{1} \\ F_{0} \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right]$$
若$n = 3$，則 $$\left[ \begin{array}{cc} F_{3} \\ F_{2} \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] \left[ \begin{array}{cc} F_{2} \\ F_{1} \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] \left[ \begin{array}{cc} F_{1} \\ F_{0} \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] ^2 \left[ \begin{array}{cc} 1\\ 0 \end{array} \right]$$
以此類推，可以寫成
$$\left[ \begin{array}{cc} F_{n} \\ F_{n - 1} \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] ^{n - 1} \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right]$$
　　萬惡的次方出現了！接著就是來好好處理矩陣的$(n - 1)$次方，有什麼化簡的方式呢？矩陣「對角化」是個很棒的選擇，但因這當中的證明與計算，是大學課程的線性代數範圍，筆者在此概略說明，計算與證明在此處不提，假設矩陣可以化為下面形式：
$$\left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}$$ 其中$\mathbf{P}$與$\mathbf{D}$均為$(2 \times 2)$維度的矩陣，$\mathbf{P}^{-1}$是$\mathbf{P}$的反矩陣，$\mathbf{D}$是對角矩陣，也就是$\mathbf{D}$中元素除了左上至右下的對角斜線位置，其餘均為0。對角化求出
$$\mathbf{P} = \left[ \begin{array}{cc} \lambda_{1} & \lambda_{2} \\ 1 & 1 \end{array} \right] \qquad \mathbf{D} = \left[ \begin{array}{cc} \lambda_{1} & 0 \\ 0 & \lambda_{2} \end{array} \right] \qquad \mathbf{P}^{-1} = \frac{1}{\lambda_{1} - \lambda_{2}} \left[ \begin{array}{cc} 1 & -\lambda_{2} \\ -1 & \lambda_{1} \end{array} \right]$$
當中的$\lambda_{1}$與$\lambda_{2}$分別為
$$\lambda_{1} = \frac{1 + \sqrt{5}}{2} \qquad \lambda_{2} = \frac{1 - \sqrt{5}}{2}$$
不相信的可以自己驗算看看，或者自己找「特徵值」與「特徵向量」的資料參考。最終可得
$$\begin{eqnarray} \left[ \begin{array}{cc} F_{n} \\ F_{n - 1} \end{array} \right] & = & (\mathbf{P}\mathbf{D}\mathbf{P}^{-1})^{n-1} \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right] \\ & = & (\mathbf{P}\mathbf{D}\mathbf{P}^{-1})(\mathbf{P}\mathbf{D}\mathbf{P}^{-1}) ... (\mathbf{P}\mathbf{D}\mathbf{P}^{-1}) \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right] \\ & = & \mathbf{P}\mathbf{D}(\mathbf{P}^{-1}\mathbf{P})\mathbf{D}(\mathbf{P}^{-1}\mathbf{P}) ... (\mathbf{P}^{-1}\mathbf{P})\mathbf{D}\mathbf{P}^{-1} \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right] \\ & = & \mathbf{P}\mathbf{D}^{n - 1}\mathbf{P}^{-1} \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right] \\ & = & \left[ \begin{array}{cc} \lambda_{1} & \lambda_{2} \\ 1 & 1 \end{array} \right] \left[ \begin{array}{cc} \lambda_{1} & 0 \\ 0 & \lambda_{2} \end{array} \right]^{n - 1} \biggl( \frac{1}{\lambda_{1} - \lambda_{2}} \left[ \begin{array}{cc} 1 & -\lambda_{2} \\ -1 & \lambda_{1} \end{array} \right] \biggr) \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right] \\ \end{eqnarray}$$
當然，只需要關心$F_{n}$，依上式可表示為
$$\begin{eqnarray} F_{n} & = & \left[ \begin{array}{cc} \lambda_{1} & \lambda_{2} \end{array} \right] \left[ \begin{array}{cc} \lambda_{1} & 0 \\ 0 & \lambda_{2} \end{array} \right]^{n - 1} \biggl( \frac{1}{\lambda_{1} - \lambda_{2}} \left[ \begin{array}{cc} 1 \\ -1 \end{array} \right] \biggr) \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right] \times 1 \\ & = & \left[ \begin{array}{cc} \lambda_{1} & \lambda_{2} \end{array} \right] \left[ \begin{array}{cc} \lambda_{1}^{n - 1} & 0 \\ 0 & \lambda_{2}^{n - 1} \end{array} \right] \biggl( \frac{1}{\lambda_{1} - \lambda_{2}} \left[ \begin{array}{cc} 1 \\ -1 \end{array} \right] \biggr) \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right] \times 1 \\ & = & \frac{1}{\lambda_{1} - \lambda_{2}} (\lambda_{1}^{n} - \lambda_{2}^{n}) \end{eqnarray}$$
代入$\lambda_{1}$與$\lambda_{2}$的數值簡化後，就能得到
$$F_{n} = \frac{\sqrt{5}}{5} \biggl[ \biggl( \frac{1 + \sqrt{5}}{2} \biggr) ^{n} - \biggl( \frac{1 - \sqrt{5}}{2} \biggr) ^{n} \biggr]$$
得證！完畢！好累！

本篇參考：
費布那西數列(Fibonacci)