フィボナッチ数列

フィボナッチ数列（ふぃぼなっちすうれつ）にはさまざまな定義があり、人によって理解のしかたが異なるので、説明が難しい。

概要

素朴な定義としては、数論的なものがある。「初項が１で次項も１、そこから先は前前項と前項の和」という説明である。
{1, 1, 2, 3, 5, 8, 13, 21, 34, ……} と続く。

以下の仮定を置く、ウサギの数として説明することもある。

• 1年目に0歳のウサギが1匹いる。
• ウサギは2歳になると、1匹の子ウサギ(0歳)を産む。(一匹なのに産むなんて無性生殖じゃねぇか、ということは考えない。)

つまり、バイバインより少し増加速度の遅いウサギである。
このとき、数列はn年目のウサギの数になっている。

漸化式による一般化

3項間漸化式として記述し、解くことを考える。

漸化式による表現

フィボナッチ数列は、漸化式を用いて以下のように表現できる。

• $a(n+2)=a(n+1)+a(n)$
• $a(1)=a(2)=1$(初期値)

特性方程式

一つ目の式より、特性方程式

• $a^{2}-a-1=0$

を得る。この二次方程式の解は2次方程式の解の公式より

• $a={\frac {1\pm {\sqrt {1+4}}}{2}}={\frac {1\pm {\sqrt {5}}}{2}}$

となって黄金比と、その有理数からみた共役な無理数が出てくる。
ここで、以下でよく使う黄金比$\varphi ={\frac {1+{\sqrt {5}}}{2}}$の性質を述べておく。黄金比は特性方程式の解だったので、
$\varphi ^{2}-\varphi -1=0$より$\varphi ^{2}-\varphi =1$であり、$\varphi -1=\varphi ^{-1}$
また、${\frac {1-{\sqrt {5}}}{2}}=1-\varphi =-\varphi ^{-1}$

第一の書き換え

よって、黄金比を用いて漸化式は次のように書き換えられる。

• $a(n+2)-\varphi a(n+1)=(1-\varphi )(a(n+1)-\varphi a(n))$

ここで、$b(n)=a(n+1)-\varphi a(n)$という数列を導入すると、等比数列の問題に帰着できて

• $b(n+1)=(1-\varphi )b(n)$
• $b(1)=a(2)-\varphi a(1)=1-\varphi$(初期値)

である。これを等比数列の問題として解くと、

• $b(n)=b(1)(-\varphi ^{-1})^{n-1}=(1-\varphi )^{n}$

さらに、$b(n)=a(n+1)-\varphi a(n)$より$a(n+1)=\varphi a(n)+b(n)$なので

• $a(n+1)=\varphi a(n)+(1-\varphi )^{n}$

第二の書き換え

また、漸化式は次のようにも書き換えられる。

• $a(n+2)-(1-\varphi )a(n+1)=\varphi (a(n+1)-(1-\varphi )a(n))$

ここで、$c(n)=a(n+1)-(1-\varphi )a(n)$という数列を導入すると、等比数列の問題に帰着できて

• $c(n+1)=\varphi c(n)$
• $c(1)=a(2)-(1-\varphi )a(1)=\varphi$(初期値)

である。これを等比数列の問題として解くと、

• $c(n)=c(1)\varphi ^{n-1}=\varphi ^{n}$

さらに、$c(n)=a(n+1)-(1-\varphi )a(n)$より$a(n+1)=(1-\varphi )a(n)+c(n)$なので

• $a(n+1)=(1-\varphi )a(n)+\varphi ^{n}$

結果の結合

上記より、

• $a(n+1)=\varphi a(n)+(1-\varphi )^{n}$
• $a(n+1)=(1-\varphi )a(n)+\varphi ^{n}$

よって、

• $(1-\varphi )a(n+1)=\varphi (1-\varphi )a(n)+(1-\varphi )^{n+1}$
• $\varphi a(n+1)=\varphi (1-\varphi )a(n)+\varphi ^{n+1}$

2式の差から

• $(2\varphi -1)a(n+1)=\varphi ^{n+1}-(1-\varphi )^{n+1}$

よって、

• $a(n+1)={\frac {\varphi ^{n+1}-(1-\varphi )^{n+1}}{2\varphi -1}}$

n+1をnにして、また黄金比を代入すると、

• $a(n)={\frac {{\frac {1+{\sqrt {5}}}{2}}^{n}-{\frac {1-{\sqrt {5}}}{2}}^{n}}{\sqrt {5}}}$

となった。これが答えである。実際にn=1,2,3と代入していくと確かにあっている。

結果の考察

このことから、一般式に無理数が含まれていても整数の数列になる数列が存在することがわかる。

さらにnが十分に大きければ、 $|{\frac {1+{\sqrt {5}}}{2}}|>1$,$|{\frac {1-{\sqrt {5}}}{2}}|<1$より、近似的に $a(n+1)=\varphi a(n)$となって、フィボナッチ数列は指数関数的に爆発していることがわかる。 $1<\varphi ={\frac {1+{\sqrt {5}}}{2}}<2$なので、バイバインよりは少しマシなウサギという説明に合致する。

人間生活との関わり・利用

ソフトウェア業界に入ると、プログラミング研修において最初にやらされるのがユークリッドの互除法であるが、このあたりは解っている奴は五分もかからずにプログラムを書き上げてしまうので、頭の悪い上司に目をつけられてハラスメントの標的になったりする。