フィボナッチ数列の基本
ウサギの問題
フィボナッチ数列は、中世の商人フィボナッチによる『算盤の書』にある問題がもととなった数列である。下にその問題を改めたものを記す。
ある男が生後間もない1番の兎を囲いの中に飼い始めた。この兎は生後1か月で成人し、生後2か月目から毎月1番の子を生む。このとき、1年後にウサギは何番になるか。
ウサギの増え方は以下の表のようになる。
$ \begin{array}{c|ccccccccccccc} n(か月)&1&2&3&4&5&6&7&8&9&10&11&12&13\\ \hline 子&1&0&1&1&2&3&5&8&13&21&34&55&89\\ 大人&0&1&1&2&3&5&8&13&21&34&55&89&144\\ 総数&1&1&2&3&5&8&13&21&34&55&89&144&233 \end{array} $
したがって、１年後のウサギは233番になる。
漸化式と一般項
この問題の$n$か月目のウサギの番の数を$F_n$で表す。この表を眺めれば前月と前々月の数を足したものが今月の数となることがわかるだろう。ここから、フィボナッチ数列の漸化式がわかる。
フィボナッチ数列$(F_n)$は以下の漸化式で定義される数列である。
$$
F_n=F_{n-1}+F_{n-2},\ F_1=F_2=1
$$
さらに、この漸化式から一般項が導ける。以下で用いられる$\phi=\frac{1+\sqrt{5}}{2}$は黄金数と呼ばれる。
フィボナッチ数列$(F_n)$の一般項は以下の通り。ただし、$\phi=\frac{1+\sqrt{5}}{2}$とする。
$$
F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)=\frac{1}{\sqrt{5}}\left(\phi ^n-(-\phi)^{-n}\right)
$$
漸化式は以下のように式変形できる。
$$
F_n-\phi F_{n-1}=(1-\phi)(F_{n-1}-\phi F_{n-2})
$$
ここで数列$(F_{n}-\phi F_{n-1})$は$n=1$のとき$1$、公比$(1-\phi)$の等比数列であるから
$$
F_n-\phi F_{n-1}=(1-\phi)^{n-1}
$$
が導ける。また、
$$
F_n-(1-\phi) F_{n-1}=\phi(F_{n-1}-(1-\phi) F_{n-2})
$$
とも変形できるので、同様にして、
$$
F_n-(1-\phi)F_{n-1}=\phi^{n-1}
$$
となる。したがって以下の連立方程式が得られる。
$$
\begin{cases}
F_n-\phi F_{n-1}=(1-\phi)^{n-1}\\
F_n-(1-\phi)F_{n-1}=\phi^{n-1}
\end{cases}
$$
両辺の差をとれば
$$
-\sqrt{5}F_{n-1}=-\phi^{n-1}+(1-\phi)^{n-1}
$$
したがって
$$
F_n=\frac{1}{\sqrt{5}}(\phi^{n}-(1-\phi)^{n})=\frac{1}{\sqrt{5}}(\phi^{n}-(-\phi)^{-n})
$$
負数番について
フィボナッチ数列はもともとウサギの数であるから、-2か月目のようなものはないが、漸化式を用いれば負数番も考えられる。一般項で考えてもやはり同じ結果になる。
$ \begin{array}{c|ccccccccccccc} n&-6&-5&-4&-3&-2&-1&0&1&2&3&4&5&6\\ \hline F_n&-8&5&-3&2&-1&1&0&1&1&2&3&5&8 \end{array} $
フィボナッチ数列の負数番が必要ならこれを使うことになる。また、フィボナッチ数列の初項を$F_1$でなく$F_0$からはじめる人もいる。