スマートフォン用の表示で見る

フィボナッチ数列

サイエンス

フィボナッチ数列

ふぃぼなっちすうれつ

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, ……」と、いわゆる黄金比 ¥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 程度と長いのが特徴。