F_{n + 1} = F_{n} + F_{n - 1}, F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}

フィボナッチ数列

Fibonacci sequence

壁に囲まれた 1 つがいのウサギは、1 年で何つがいになるか。

前の 2 項を足して次の項を作る数列。1, 1, 2, 3, 5, 8, … と進み、隣どうしの比は黄金比に近づく。植物の螺旋や計算の速さの見積もりに現れる。

年代: 1202年
人物: レオナルド・フィボナッチ、ヘーマチャンドラ、ヨハネス・ケプラー、ジャック・ビネ、エドゥアール・リュカ

数学生物学情報科学言語学

逸話

壁の中のウサギ

1202 年、ピサの商人の息子レオナルドは、計算の教科書『算盤の書(リベル・アバチ)』を書き上げた。父グリエルモ・ボナッチは、ピサの商人のための役人として北アフリカのブジア(今のアルジェリアのベジャイア)に赴任しており、レオナルドは少年のころそこでインドの数字(今の算用数字)による計算を学んだ。その後エジプト、シリア、ギリシア、シチリアなどを商用で回り、各地の計算法を集めた。本はその成果である。冒頭に著者は「ボナッチの息子(フィリウス・ボナッチ)ピサのレオナルド」と名乗っている。フィボナッチという呼び名は、この「フィリウス・ボナッチ」を縮めたもので、後の時代に広まった。

第 12 章に、こんな問題がある。ある人が、四方を壁に囲まれた場所に 1 つがいのウサギを置いた。どのつがいも毎月 1 つがいの子を産み、生まれたつがいは 2 か月目から子を産むとする。1 年で何つがいになるか。

レオナルドは月ごとに数を書き出していく。最初のつがいが 1 か月目に子を産んで 2 つがい、2 か月目に 3 つがい、それから 5、8、13、21、34、55、89、144、233 と増え、12 か月目に 377 つがいになる。欄外には、この数が縦に並べて書かれている。前の 2 つの数を足せば次の数になること、この手順を限りなく続けられることも本文に書いてある。

ウサギの問題は、数の並びを教えるための練習問題だった。本物のウサギはこのようには増えない。死なず、いつも雄と雌の 1 つがいずつ生まれるという仮定は、生物の観察から来たものではない。

1225 年ごろ、神聖ローマ皇帝フリードリヒ 2 世がピサを訪れたとき、宮廷の学者ヨハネス・パノルミターヌスがレオナルドに難問を出した。5 を足しても引いても平方数になる平方数を見つけよ。レオナルドは $(\frac{41}{12})^{2}$ を答えた。 $5$ を足すと $(\frac{49}{12})^{2}$ 、引くと $(\frac{31}{12})^{2}$ になる。このやりとりは、レオナルドが皇帝に献じた『平方の書』(1225)に記されている。

起源

この数列は、ヨーロッパより先にインドで、詩の韻律を数える問題から現れた。

サンスクリットの詩では、短い音節を 1 拍、長い音節を 2 拍と数える。合わせて $n$ 拍になる短長の並べ方は何通りあるか。最後が短い音節なら残りは $n - 1$ 拍、長い音節なら残りは $n - 2$ 拍なので、並べ方の数は前の 2 つの数の和になる。紀元前のピンガラの韻律の書にこの数え方の糸口があり、6〜8 世紀ごろのヴィラハーンカ、1135 年ごろのゴーパーラ、1150 年ごろのヘーマチャンドラが、和の規則をはっきり書き残した。いずれもレオナルドの本より早い。

ヨーロッパでは、1611 年にヨハネス・ケプラーが雪の結晶を論じた小冊子『六角形の雪について』で、5 と 8、8 と 13 のように隣り合う数の比が神聖比例、つまり黄金比に近づくことを書いた。1753 年にはスコットランドのロバート・シムソンがこれを証明した。

一般の項を直接書く式 $F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}$ は、1843 年にフランスのジャック・ビネが発表したのでビネの公式と呼ばれる。ただし 18 世紀にド・モアブル、ダニエル・ベルヌーイ、オイラーがすでに知っていた。

「フィボナッチ数列」という名前を付けたのは、19 世紀フランスのエドゥアール・リュカである。リュカは 1870 年代にこの数列の約数の性質を詳しく調べ、素数の判定に使った。1963 年にはこの数列だけを扱う専門誌『フィボナッチ・クォータリー』が創刊され、今も続いている。

証明

$F_{0} = 0$ , $F_{1} = 1$ , $F_{n + 1} = F_{n} + F_{n - 1}$ からビネの公式を導く。

等比数列の形 $F_{n} = r^{n}$ で漸化式を満たすものを探す。代入して $r^{n - 1}$ で割ると
$r^{2} = r + 1$
この二次方程式の解は 2 つある。
$φ = \frac{1 + 5}{2} = 1.618 \dots, ψ = \frac{1 - 5}{2} = - 0.618 \dots$
漸化式は足し算と定数倍で閉じているので、2 つの組み合わせも漸化式を満たす。
$F_{n} = A φ^{n} + B ψ^{n}$
$F_{0} = 0$ から $A + B = 0$ 。 $F_{1} = 1$ から $A (φ - ψ) = 1$ で、 $φ - ψ = 5$ なので
$A = \frac{1}{5}, B = - \frac{1}{5}$
よって
$F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}$
$∣ ψ ∣ < 1$ なので $ψ^{n}$ はすぐに 0 に近づく。隣の項の比は
$\frac{F _{n + 1}}{F _{n}} = \frac{φ ^{n + 1} - ψ ^{n + 1}}{φ ^{n} - ψ ^{n}} \to φ$

無理数ばかりの式から、いつも整数が出てくる。 $ψ^{n}$ の影響は小さいので、 $F_{n}$ は $\frac{φ ^{n}}{5}$ をいちばん近い整数に丸めたものに等しい。たとえば $\frac{φ ^{10}}{5} = 55.0036 \dots$ で、 $F_{10} = 55$ である。

もう 1 つ、1680 年にジョヴァンニ・カッシーニが示した等式 $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ がある。 $8 \times 8$ の正方形を切って $5 \times 13$ の長方形に並べ直すと、面積が 64 から 65 に増えたように見える手品は、 $13 \times 5 - 8^{2} = 1$ のずれを細い隙間に隠している。

応用

計算の手間の上限。 2 つの整数の最大公約数を求めるユークリッドの互除法は、隣り合うフィボナッチ数を与えたときに最も手間がかかる。89 と 55 では割り算が 9 回必要になる。1844 年、ガブリエル・ラメはこの性質を使い、割り算の回数は小さい方の数の桁数の 5 倍を超えないことを証明した。計算の手間を数学的に見積もった、最も早い例の 1 つとされる。

マイルとキロ。 1 マイルは 1.609 km で、黄金比 1.618 に近い。そのため隣り合うフィボナッチ数で、5 マイルはほぼ 8 km(正しくは 8.05 km)、8 マイルはほぼ 13 km(12.87 km)、13 マイルはほぼ 21 km(20.92 km)と換算できる。

ヒマワリの螺旋。 ヒマワリの種は、右回りと左回りの螺旋に並ぶ。その本数は 34 と 55、55 と 89 のような隣り合うフィボナッチ数になることが多い。ただし、いつもそうなるわけではない。イギリスで市民が育てた 657 本のヒマワリを数えた研究(2016 年発表)では、確実に数えられた 768 の螺旋の本数のうち、フィボナッチ数だったのは 565(約 74%)だった。残りには、フィボナッチ数より 1 少ない数などが混じっていた。なぜ多くの場合にフィボナッチ数になるかは、黄金角と葉序の記事で扱う。

図示

1 辺が 1, 1, 2, 3, 5, 8, 13 の正方形を、回りながら継ぎ足していく。どの段階でも全体は長方形で、縦と横は隣り合うフィボナッチ数になる。各正方形に 4 分の 1 の円を描いてつなぐと、螺旋になる。

13 × 21 の長方形の縦横の比は 1.615 で、黄金比 1.618 にかなり近い。正方形を足すたびに、比は黄金比を上下から挟みながら近づいていく。

シミュレーション

「正方形」では、正方形が 1 つずつ継ぎ足され、全体の縦横の比が黄金比に近づいていく様子が読み取り欄に出る。「ウサギ」では、『算盤の書』の問題の通りに、月ごとにつがいが増えていく。黒い丸は子を産むつがい、白い丸は生まれたばかりのつがいである。つまみ $n$ で正方形の数や月を変えられる。

広がる学問

数学線形の漸化式を等比数列で解く方法は、この数列で最もよく知られる。リュカが調べた約数の性質は、大きな数が素数かどうかを判定する方法に受け継がれた。どの正の整数も、隣り合わないフィボナッチ数の和でただ 1 通りに書ける(ツェッケンドルフの定理。たとえば $100 = 89 + 8 + 3$ )。
生物学 植物の葉や種の並び方(葉序)では、螺旋の本数にフィボナッチ数がよく現れる。新しい芽が、前の芽からほぼ一定の角度だけずれて出ることから説明される。一方で、オウムガイの殻や人体の比率を黄金比と結びつける話の多くは、測ってみると合わない。
情報科学 ラメの定理は計算量の解析の先駆けになった。データ構造のフィボナッチヒープ(1984 年発表)は、木の大きさがフィボナッチ数で抑えられることを使い、最短経路を求める計算を速くする。
言語学 インドの韻律学では、拍の数が決まった詩の型を数える問題として、この数列が数百年にわたって研究された。音節の長短の並べ方を数える方法は、詩の韻律を調べる韻律論の道具として使われてきた。

参考文献

L. E. Sigler (trans.), Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation (Springer, 2002).
Parmanand Singh, "The So-called Fibonacci Numbers in Ancient and Medieval India", Historia Mathematica 12 (1985), 229-244.
Keith Devlin, The Man of Numbers: Fibonacci's Arithmetic Revolution (Walker, 2011).
Jonathan Swinton, Erinma Ochu, and the MSI Turing's Sunflower Consortium, "Novel Fibonacci and non-Fibonacci structure in the sunflower: results of a citizen science experiment", Royal Society Open Science 3 (2016), 160091.
Donald E. Knuth, The Art of Computer Programming, Vol. 1, 3rd ed. (Addison-Wesley, 1997), Section 1.2.8.

フィボナッチ数列

壁の中のウサギ

起源

証明

応用

図示

シミュレーション

広がる学問

参考文献

タグ

同じタグを持つ公式

姉妹サイト