フィボナッチ数列

フィボナッチ数列とは、
\begin{eqnarray}
F_0 &=& 0 \\
F_1 &=& 1 \\
F_{n+2} &=& F_{n+1} + F_n \qquad (n \ge 0)
\end{eqnarray}
で定義される数列のことです。

一般的にはとしますが、後の計算を簡単にするために、を採用しています。どちらも、を除き、同じ数列が得られます。

一般項を求めてみます。
3項間漸化式 - 数式で独楽する
に沿って求めることができます。

まず、
\begin{equation}
\left \{
\begin{array}{l}
1 = \alpha + \beta \\
1 = - \alpha \beta
\end{array}
\right.
\end{equation}を満たすを定めます。
このは、2次方程式
\begin{equation}
x^2=x+1
\end{equation}の解になっています。つまり、
\begin{equation}
\alpha, \beta = \frac{1 \pm \sqrt{5}}{2}
\end{equation}ということです。
以下、
\begin{eqnarray}
\alpha &=& \frac{1 + \sqrt{5}}{2} \\
\beta &=& \frac{1 - \sqrt{5}}{2}
\end{eqnarray}
としておきます。

さて、を用いると、漸化式は次のようになります。
\begin{equation}
F_{n+2} = (\alpha + \beta )F_{n+1} - \alpha \beta F_n
\end{equation}
この式は、2通りに変形できます。
\begin{equation}
\left \{
\begin{array}{l}
F_{n+2} - \alpha F_{n+1} = \beta (F_{n+1} - \alpha F_n ) \\
F_{n+2} - \beta F_{n+1} = \alpha (F_{n+1} - \beta F_n )
\end{array}
\right.
\end{equation}
この形は、数列が等比数列であることを示しています。
したがって、
\begin{equation}
\left \{
\begin{array}{l}
F_{n+1} - \alpha F_n = \beta ^n (F_1 - \alpha F_0 ) \\
F_{n+1} - \beta F_n = \alpha ^n (F_1 - \beta F_0 )
\end{array}
\right.
\end{equation}ここで、なので、
\begin{equation}
\left \{
\begin{array}{l}
F_{n+1} - \alpha F_n = \beta ^n \\
F_{n+1} - \beta F_n = \alpha ^n
\end{array}
\right.
\end{equation}
となります。

辺々相引くと、が消えます。
\begin{equation}
(\alpha - \beta )F_n = \alpha ^n - \beta ^n
\end{equation}

両辺をで割ると、一般項
\begin{equation}
F_n = \frac{\alpha ^n - \beta ^n}{\alpha - \beta }
\end{equation}を得ることができます。
式中のに数値を入れると、
\begin{equation}
F_n = \frac{1}{\sqrt{5}} \left \{ \left( \frac{1 + \sqrt{5}}{2} \right) ^n - \left( \frac{1 -\sqrt{5}}{2} \right) ^n \right \}
\end{equation}となります。
数列の各項は整数であるにもかかわらず、項数で表すと無理数が現れる、不思議な数列です。

ところで、は黄金数そのものであり、もで表すことができます。つまり、
\begin{eqnarray}
\alpha &=& \phi \\
\beta &=& 1 -\phi
\end{eqnarray}
です。これを用いて、
\begin{equation}
F_n = \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}
\end{equation}と書くことができます。

また、
\begin{equation}
\phi = 1 + \frac{1}{\phi}
\end{equation}であることから、
\begin{equation}
\beta = - \frac{1}{\phi}
\end{equation}とも表せます。これを用いると、
\begin{equation}
F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}
\end{equation}と書くことができます。

まとめ

\begin{eqnarray}
F_0 &=& 0 \\
F_1 &=& 1 \\
F_{n+2} &=& F_{n+1} + F_n \qquad (n \ge 0)
\end{eqnarray}
であるとき、
\begin{eqnarray}
F_n &=& \frac{1}{\sqrt{5}} \left \{ \left( \frac{1 + \sqrt{5}}{2} \right) ^n - \left( \frac{1 -\sqrt{5}}{2} \right) ^n \right \} \\
F_n &=& \frac{\phi^n - (1-\phi)^n}{\sqrt{5}} \\
F_n &=& \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}
\end{eqnarray}