Hatena Blog Tags

フィボナッチ数列

(サイエンス)
ふぃぼなっちすうれつ

12〜13世紀のイタリアの数学者ピサのレオナルド・フィリオ・ボナッチ(通称「フィボナッチ」)が考えた「ネズミ算」ならぬ「ウサギ算」から導かれる数列のこと。

「1対の子ウサギが居て、子ウサギは1ヶ月たつと親ウサギになり、その1ヶ月後には1対の子ウサギを生むようになる。どの対のウサギも死なないものとすれば、1年間に何対のウサギが生まれるか?」という問題を考える。計算すると「1, 1, 2, 3, 5, 8, 13, 21, 34, ……」とウサギの対は1ヶ月ごとに増加していく。また、その際の増加数は「1, 2, 3, 5, 8, 13, 21, ……」と輪唱していくわけで、その増加率は「1, 2, 1.5, 1.666, 1.6, 1.625, 1.615, 1.619, ……」と、いわゆる黄金比 [tex:\frac{1+\sqrt{5}}{2}] = 1.6180339... に収束していく。

漸化式は F_n = F_{n-1} + F_{n-2} である。F_nF_{n-1}を縦に並べたベクトルの漸化式を書くと、\left(\begin{array}{c}F_{n+1}\\F_{n}\end{array}\right) = \left(\begin{array}{c}F_{n}+F_{n-1}\\F_{n}\end{array}\right) = \left[\begin{array}{cc}1&1\\1&0\end{array}\right] \left(\begin{array}{c}F_{n}\\F_{n-1}\end{array}\right)となり、行列\left[\begin{array}{cc}1&1\\1&0\end{array}\right]を左から掛けていくことになる。この行列の固有値は\frac{1\pm\sqrt{5}}{2}で、この一方の固有値に比率は漸近していく。

><

漸化式を一般化した  F_n = F_{n-p} + F_{n-q} は Lagged フィボナッチ数列(ラグ付フィボナッチ数列)と呼ばれ、乱数生成に使われることがある。周期が 2^q 程度と長いのが特徴。

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

ネットで話題

もっと見る

関連ブログ