2015/10/28

費氏數列-等比推導篇

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

沒有留言:

張貼留言