費氏數列-等比推導篇

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

　　在《費氏數列-矩陣推導篇》介紹過費氏數列：$1, 1, 2, 3, 5, 8, 13, 21, \dots$，以及使用「線性代數」的數學知識，求出$F_{n}$的通式，對於沒修過「線性代數」或「矩陣」的讀者來說不容易理解，這篇會用台灣教育的國中程度能夠一目了然的方法，求出$F_{n}$的通式。

　　定義一個「類費氏數列$F'$」，擁有與費氏數列「後項是前兩項之和」的特質，但起始值為$a_{1}$與$a_{2}$，也就是
$$\begin{eqnarray} F'_{1} &=& a_{1} \\ F'_{2} &=& a_{2} \\ F'_{3} &=& F'_{1} + F'_{2} = a_{1} + a_{2} \\ F'_{4} &=& F'_{2} + F'_{3} = a_{2} + (a_{1} + a_{2}) = a_{1} + 2a_{2} \\ F'_{5} &=& F'_{3} + F'_{4} = (a_{1} + a_{2}) + (a_{1} + 2a_{2}) = 2a_{1} + 3a_{2} \\ &\vdots& \end{eqnarray}$$
寫成數列的形式就是
$$a_{1}, a_{2}, ( a_{1} + a_{2} ), ( a_{1} + \color{aqua}{2} a_{2} ), ( \color{aqua}{2} a_{1} + \color{aqua}{3} a_{2} ), ( \color{aqua}{3} a_{1} + \color{aqua}{5} a_{2} ), ( \color{aqua}{5} a_{1} + \color{aqua}{8} a_{2} ), \dots$$
不難發現「類費氏數列$F'$」從第3項起，即項數$n \ge 3$時，$F'_{n}$是用起始值為$a_{1}$、$a_{2}$以及「費氏數列$F$」的項組合而成
$$F'_{n} = a_{1} \color{aqua}{F_{n - 2}} + a_{2} \color{aqua}{F_{n - 1}}$$
而當$a_{1} = a_{2} = 1$時，此「類費氏數列$F'$」正是「費氏數列$F$」本身。

　　若某數$x$滿足$x^{2} = x + 1$，此時等比數列
$$x, x^{2}, x^{3}, x^{4}, x^{5}, \dots$$
將會是一個「類費氏數列」，因為當項數$n \ge 3$時，
$$\begin{eqnarray} x^{n} &=& x^{n - 2} \times x^{2} \\ &=& x^{n - 2} \times (x + 1) \\ &=& x^{n - 1} + x^{n - 2} \end{eqnarray}$$
符合「後項是前兩項之和」的特性，此數列在類費氏數列的起始值為$a_{1} = x$、$a_{2} = x^{2}$，可以推得
$$\begin{eqnarray} F'_{n} &=& a_{1} \color{aqua}{F_{n - 2}} + a_{2} \color{aqua}{F_{n - 1}} \\ x^{n} &=& x \color{aqua}{F_{n - 2}} + x^{2} \color{aqua}{F_{n - 1}} \\ &=& x \color{aqua}{F_{n - 2}} + (x + 1) \color{aqua}{F_{n - 1}} \\ &=& x \color{aqua}{( F_{n - 2} + F_{n - 1} )} + \color{aqua}{F_{n - 1}} \\ &=& x \color{fuchsia}{F_{n}} + \color{aqua}{F_{n - 1}} \end{eqnarray}$$
一元二次方程式$x^{2} = x + 1$，可用配方法求出$x$之解： $$\begin{eqnarray} x^{2} &=& x + 1 \\ x^{2} \color{aqua}{ - x + { \biggl( \frac{1}{2} \biggr) }^{2} } &=& x + 1 \color{aqua}{ - x + { \biggl( \frac{1}{2} \biggr) }^{2} } \\ { \biggl( x - \frac{1}{2} \biggr) }^{2} &=& \frac{5}{4} \\ x &=& \frac{1}{2} \pm \sqrt{ \frac{5}{4} } = \frac{ 1 \pm \sqrt{5}}{2} \end{eqnarray}$$
將$x$的兩個解用$\lambda_{1}$與$\lambda_{2}$表示
$$\lambda_{1} = \frac{1 + \sqrt{5}}{2}, \qquad \lambda_{2} = \frac{1 - \sqrt{5}}{2}$$
是否覺得這個配方法有點熟悉？沒錯，$\lambda_{1}$正是在《費氏數列-黃金比例篇》所提到的黃金比例$\phi$！

　　將$x$等於$\lambda_{1}$與$\lambda_{2}$，分別代入由前面所推導的結果，衍生出以下兩個方程式
$$\begin{eqnarray} \lambda_{1}^{n} &=& \lambda_{1} \color{fuchsia}{F_{n}} + \color{aqua}{F_{n - 1}} \\ \lambda_{2}^{n} &=& \lambda_{2} \color{fuchsia}{F_{n}} + \color{aqua}{F_{n - 1}} \end{eqnarray}$$
將兩式相減，得到
$$\lambda_{1}^{n} - \lambda_{2}^{n} = \bigl( \lambda_{1} - \lambda_{2} \bigr) \color{fuchsia}{F_{n}}$$
又因為$\lambda_{1}$與$\lambda_{2}$相異，可以做上式左右兩邊同除以$\bigl( \lambda_{1} - \lambda_{2} \bigr)$，整理後得到
$$\color{fuchsia}{F_{n}} = \frac{1}{\lambda_{1} - \lambda_{2}} \bigl( \lambda_{1}^{n} - \lambda_{2}^{n} \bigr)$$
將$\lambda_{1}$與$\lambda_{2}$之值代入，即得到$F$數列第$n$項的通式為
$$\color{fuchsia}{F_{n}} = \frac{1}{\lambda_{1} - \lambda_{2}} \bigl( \lambda_{1}^{n} - \lambda_{2}^{n} \bigr) = \frac{\sqrt{5}}{5} \biggl[ \biggl( \frac{1 + \sqrt{5}}{2} \biggr) ^{n} - \biggl( \frac{1 - \sqrt{5}}{2} \biggr) ^{n} \biggr]$$

※本篇為筆者參考前人智慧的結晶，自行修改的推導方法，若要引用請註明出處。


本篇參考：
維基百科-費氏數列
費氏數列及黃金分割(第3頁)