D04 フィボナッチ数列

F₁ = 1

F₂ = 1

F_n+2 = F_n+1 + F_n (n = 1,2,...)

で定義されるフィボナッチ数列の一般項を返すコマンドを3通りの方法で作成してみます。

行列のn乗を用いる方法

n = 8

m = x({ {1,1},{1,0} }^n (0,1))

本質的には３項間漸化式で述べた方法ですが、漸化式に定数項がないので2次の行列でプログラムでき、初期値を与える2次の列ベクトルの代わりに点の座標を用いています。出力オブジェクト m、入力オブジェクト n でツールも作成できます。

漸化式を解いた一般項を用いる方法

φ=(1+√5)/2 を黄金比とすると、フィボナッチ数列の第n項は、

F_n = (φⁿ - (-φ)^-n ) / √5

と書けることを利用すると、次のようにも定義できます。

n = 8

gr = (1+sqrt(5))/2

m = (gr^n - (-gr)^(-n)) / sqrt(5)

近似値を用いる方法

φ^-n は0に近いことを利用すると、

F_n = (φⁿ / √5 + 0.5) の整数部分

とも書けるので、

n = 8

m = floor( (1+sqrt(5))^n / (2^n sqrt(5)) + 0.5 )

とも定義できます。先ほどよりも誤差を吸収してくれる可能性はあります。