フィボナッチ数列

前の2項を足すと次の数になる数列。

$1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 \cdots$

ちなみに、トリボナッチ数列（前の3項の和が次の項になる数列）、テトラナッチ数列（前の4項の和が次の項になる数列）などもある。

フィボナッチ数列における漸化式は以下のように書ける。

$$a_{n+2}=a_{n+1}+a_{n}$$

特性方程式は$x^2-x-1=0$。これを解くと

$x=\displaystyle\frac{1\pm\sqrt 5}{2}$　となるので、漸化式は次の2通りに変形可能。

①　$a_{n+2}-\displaystyle\frac{1+\sqrt 5}{2}a_{n+1}=\displaystyle\frac{1-\sqrt 5}{2}\biggl(a_{n+1}-\displaystyle\frac{1+\sqrt 5}{2}a_{n}\biggr)$

②　$a_{n+2}-\displaystyle\frac{1-\sqrt 5}{2}a_{n+1}=\displaystyle\frac{1+\sqrt 5}{2}\biggl(a_{n+1}-\displaystyle\frac{1-\sqrt 5}{2}a_{n}\biggr)$

これらは初項を考慮すると、次のように変形できる。

①は

$a_{n+1}-\displaystyle\frac{1+\sqrt 5}{2}a_{n}=\biggl(\displaystyle\frac{1-\sqrt 5}{2}\biggr)^n$

②は

$a_{n+1}-\displaystyle\frac{1-\sqrt 5}{2}a_{n}=\biggl(\displaystyle\frac{1+\sqrt 5}{2}\biggr)^n$

上から下を引いて整理すると

$a_{n}=\displaystyle\frac{1}{\sqrt 5}\biggl[\biggl(\displaystyle\frac{1+\sqrt 5}{2}\biggr)^n-\biggl(\displaystyle\frac{1-\sqrt 5}{2}\biggr)^n\biggr]$

$\displaystyle\frac{1+\sqrt 5}{2}=\phi$とおくと（黄金比）

$a_{n}=\displaystyle\frac{\phi^n-(-\phi)^{-n}}{\sqrt 5}$

フィボナッチ数列において最初の2項を 2, 1 に置き換えた数列の項を「リュカ数」といい、この数列はより美しい形で表される。

数列を$L_{n}$とおく。

$$L_{n}=\phi^n+(-\phi)^{-n}$$