フィボナッチ数列とは

「日本数学検定協会賞」受賞者の吉田 桃子さんの発表の様子

フィボナッチ数列の一般項

(1) 初期条件 $F_1 = F_2 フィボナッチ数列とは = 1$ と隣接 $3$ 項間漸化式 $F_ = フィボナッチ数列とは F_n+F_$ で定まる数列 \[\< F_n\>:1,1,2,3,5,8,13,21,34,55,89,144,\cdots\] をフィボナッチ数列(フィボナッチ数列とは Fibonacci sequence)と呼び, その項として表される整数をフィボナッチ数(Fibonacci number)と呼ぶ. (2) 初期条件 $L_1 = 1,$ $L_2 = 3$ と隣接 $3$ 項間漸化式 $L_ = L_n+L_$ で定まる数列 \[\< L_n\>:1,3,4,7,11,18,29,47,76,123,199,322,\cdots\] をリュカ数列(Lucas sequence)と呼び, その項として表される整数をリュカ数(Lucas number)と呼ぶ.

ビネの公式

定理《ビネの公式》

ビネの公式の応用

定理《フィボナッチ数列の隣接項の比》

定理《フィボナッチ数列とリュカ数列の相互関係》

定理《偶数番目のリュカ数》

ビネの公式により, \[\begin L_ &= \varphi ^+\tilde\varphi ^ = (\varphi ^n+\tilde\varphi フィボナッチ数列とは ^n)^2-2(\varphi\tilde\varphi )^n \\ &= L_n<>^2-2(-1)フィボナッチ数列とは ^n = L_n<>^2+2(-1)^ \end\] が成り立つ.

高校数学の問題

問題《リュカ数を表す対称式の値》

$\alpha = フィボナッチ数列とは \dfrac,$ $\beta = \dfrac$ について, \[\alpha +\beta, \quad \alpha\beta, \quad \alpha ^2+\beta ^2, \quad \alpha ^4+\beta ^4\] の値を求めよ.

問題《フィボナッチ数列の一般項と和》

$1$ 歩目は $1$ 段だけ上るとし, $2$ 歩目以降は $1$ 歩で $1$ 段上ることも $2$ 段上ることもできるとして, $n$ 段の階段を上る方法の総数を $F_n$ とおく. また, 同様の方法で $n$ 段以下の階段を上る方法の総数を $S_n$ とおく. (1) $F_ = F_n+F_$ が成り立つことを示せ. (2) 数列 $\< F_-\alpha F_n\>,$ $\< F_-\beta F_n\>$ がそれぞれ公比 $\beta,$ $\alpha$ の等比数列となるような定数 $\alpha,$ $\beta\ (\alpha > \beta )$ を $1$ 組求めよ. (3) 数列 フィボナッチ数列とは $\< F_n\>$ の一般項を求めよ. (4) 数列 フィボナッチ数列とは $\< S_n\>$ の一般項を求めよ.

関数と極限

問題《フィボナッチ数列の隣接項の比の極限》

$F_1 = F_2 = 1,$ $F_ = F_n+F_$ で定まる数列 $\< F_n\>$ は「フィボナッチ数列」と呼ばれ, その一般項は \[ F_n = \frac\left\<\left(\frac<1+\sqrt 5>\right) ^n-\left(\frac\right) ^n\right\>\] であることが知られている(証明はこちらを参照). この数列について, 隣り合う項の比の極限 $\lim\limits_\dfrac$ を求めよ.

フィボナッチ数列と成長の仕組みについて

たった n=5 の場合でもかなり大変なことになっています。しかし、これくらいなら、最近のCPU演算能力による力技で何とかなるのです。では、これが n=40, n=50くらいになってくるとどうでしょう。さすがに厳しくなってきます。関数の呼び出しには実際の計算と関係のないオーバーヘッドがかかります。計算量より関数呼び出しにCPU処理時間が使われていて、その結果、答えを出すのにものすごく時間が必要になってしまうのです。

「関数呼び出し」を減らそう

先程のコードでは、関数呼び出しがボトルネックになっていましたので、アルゴリズムを少し改良してみます。

改良したコードでは、一度計算した結果を data[] という配列に格納しています。こうすることで、fib2()そのものは一度しか呼び出されません。

JavaScriptに限らず、配列参照は関数呼び出しに比べてコストがかからない処理なので、高速に実行されるというわけです。

これでも良いのですが、もっといい方法はないのでしょうか？

n番目のフィボナッチ数を求める公式がある

なぜ、整数しかとるはずのないフィボナッチ数にルートが出てくるのかは、数学の奥深いところですが(※この数は「黄金比」に関係があります）、「一般式があるのだから、公式にしたがって関数をつくればいいのでは？」と思いますよね。

プログラム言語の限界

困難な問題でも、答えがあるということがわかれば対処策も必ず出てくる

あなたは、ここにアクセスしてFibonacci(103)と入力するだけで必要なフィボナッチ数の答えを得ることができます。答えを得るだけなら、アルゴリズムのボトルネックをリファクタリングしたり、ゼロからコードを書く必要はまったくないのです。

成長と進化の流れの行き着く先

今回は数学の話でしたが、何かの問題を解決しようとするとき、1)自力でシンプルに解く、2)自力でシンプルな解法を改良する、3)もっとうまくやる人に依頼する、4)専門の道具を使う、という価値変化の流れがあります。人がやっていることはいずれ道具に必ず置き換わりますので、フィボナッチ数列同様、私たちも少しずつ「成長」していきたいものですね。

関連記事