費氏數列 - 矩陣推導篇

此篇數學式使用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)