フィボナッチ数列の基本

184

ウサギの問題

フィボナッチ数列は、中世の商人フィボナッチによる『算盤の書』にある問題がもととなった数列である。下にその問題を改めたものを記す。

ある男が生後間もない1番の兎を囲いの中に飼い始めた。この兎は生後1か月で成人し、生後2か月目から毎月1番の子を生む。このとき、1年後にウサギは何番になるか。

ウサギの増え方は以下の表のようになる。

$\begin{array}{cccccccccccccc} n (か月) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ 子 & 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$

さらに、この漸化式から一般項が導ける。以下で用いられる $ϕ = \frac{1 + \sqrt{5}}{2}$ は黄金数と呼ばれる。

フィボナッチ数列の一般項（ビネーの公式）

フィボナッチ数列 $(F_{n})$ の一般項は以下の通り。ただし、 $ϕ = \frac{1 + \sqrt{5}}{2}$ とする。
$F_{n} = \frac{1}{\sqrt{5}} ({(\frac{1 + \sqrt{5}}{2})}^{n} - {(\frac{1 - \sqrt{5}}{2})}^{n}) = \frac{1}{\sqrt{5}} (ϕ^{n} - (- ϕ)^{- n})$

漸化式は以下のように式変形できる。
$F_{n} - ϕ F_{n - 1} = (1 - ϕ) (F_{n - 1} - ϕ F_{n - 2})$
ここで数列 $(F_{n} - ϕ F_{n - 1})$ は $n = 1$ のとき $1$ 、公比 $(1 - ϕ)$ の等比数列であるから
$F_{n} - ϕ F_{n - 1} = (1 - ϕ)^{n - 1}$
が導ける。また、
$F_{n} - (1 - ϕ) F_{n - 1} = ϕ (F_{n - 1} - (1 - ϕ) F_{n - 2})$
とも変形できるので、同様にして、
$F_{n} - (1 - ϕ) F_{n - 1} = ϕ^{n - 1}$
となる。したがって以下の連立方程式が得られる。
${\begin{cases} F_{n} - ϕ F_{n - 1} = (1 - ϕ)^{n - 1} \\ F_{n} - (1 - ϕ) F_{n - 1} = ϕ^{n - 1} \end{cases}$
両辺の差をとれば
$- \sqrt{5} F_{n - 1} = - ϕ^{n - 1} + (1 - ϕ)^{n - 1}$
したがって
$F_{n} = \frac{1}{\sqrt{5}} (ϕ^{n} - (1 - ϕ)^{n}) = \frac{1}{\sqrt{5}} (ϕ^{n} - (- ϕ)^{- n})$

負数番について

フィボナッチ数列はもともとウサギの数であるから、-2か月目のようなものはないが、漸化式を用いれば負数番も考えられる。一般項で考えてもやはり同じ結果になる。

$\begin{array}{cccccccccccccc} n & - 6 & - 5 & - 4 & - 3 & - 2 & - 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ F_{n} & - 8 & 5 & - 3 & 2 & - 1 & 1 & 0 & 1 & 1 & 2 & 3 & 5 & 8 \end{array}$