フィボナッチ数

フィボナッチ数は、イタリアの数学者レオナルド・フィボナッチに因んで名付けられた数である。

1. 概要
-----

フィボナッチ数列 (//Fsub は、次の漸化式で定義される：//

第0～22項の値は次の通りである：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …1202年にフィボナッチが発行した『算盤の書』 に記載されたことで「フィボナッチ数」と呼ばれているが、それ以前にもインドの学者であるヘーマチャンドラ  が韻律の研究により発見し、書物に記したことが判明している。

2. 兎の問題
-------

レオナルド・フィボナッチは次の問題を考案した。

1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む。
兎が死ぬことはない。
この条件の下で、産まれたばかりの1つがいの兎は1年の間に何つがいの兎になるか？つがいの数は次の表のようになる。どの月のつがいの合計も、その前の2つの月での合計の和となり、フィボナッチ数が現れていることが分かる。



3. 一般項
------

フィボナッチ数列の一般項は次の式で表される：

この式は1843年にビネ  が発表したことからビネの公式と呼ばれるが、それ以前の1730年・1765年にも発表されており、ビネは最初の発見者ではない。

なお、この式に現れる

は黄金数で、いくつかの数学的特徴がある。黄金数を作る二次方程式 //x//sup の解を //α//, //β// }} とすると、上記の一般項は

と表せる。

また、一般項の第2項 の絶対値は減少列で、1=//n// = 0}} のとき より、第2項を切り捨てた式は Fsub の値を 0.447 以下の誤差で与える近似式である。

この誤差の絶対値は0.5未満なので、Fsub の正確な整数値は以下の式で得られる。

ただし、 は床関数である。

なお、後述の負数番への拡張を考慮した場合、//n// < 0}} では逆に一般項の第1項の絶対値が0.5未満となるため、//n// < 0}} における Fsub の正確な整数値は以下の式で得られる。

これらのことから、任意の整数 n}} における Fsub の正確な整数値は以下の式で得られる。

ただし、sgn //x//}} は符号関数である。

また、フィボナッチ数列の漸化式は次のように行列表現できる：

母関数は

である。

4. 性質
-----

フィボナッチ数列の隣接2項の商は黄金数 φ}} に収束する。この性質は初期値  に依らない。

これは次のように導出される：

が収束するとすれば、
自然数 //p//, //q//}} の最大公約数を r}} とすると、Fsub と Fsub の最大公約数は Fsub である。これより以下を導くことができる。

m}} が n}} で割り切れるならば、Fsub は Fsub で割り切れる。
連続する2数は互いに素であることより、隣り合うフィボナッチ数も互いに素である。
Fsub が偶数となるのは m}} が 3 の倍数となるときと一致する。
Fsub が 5 の倍数となるのは m}} が 5 の倍数となるときと一致する。
p}} が 2 でも 5 でもない素数のとき、1=//m// = //p// − }} とおくと p}} は Fsub を割り切る。ここで }} はルジャンドル記号である。フィボナッチ数の累和や累積について以下の式が成り立つ。

また、次の関係式が知られている。

フィボナッチ数のうち平方数であるのは 1=//F//sub, 1=//F//sub のみ 、立方数であるのは 1=//F//sub, 1=//F//sub のみ である。フィボナッチ数のうち累乗数であるのはこれしかない 。

フィボナッチ数で素数であるのは 2, 3, 5, 13, 89, 233, 1597, 28657, … である。また、これらはフィボナッチ素数と呼ばれる。

フィボナッチ数で三角数であるのは 1, 3, 21, 55のみであることは Vern Hoggatt によって予想されていたが、のちに Luo Ming によって証明された。

フィボナッチ数でハーシャッド数であるのは 1, 2, 3, 5, 8, 21, 144, 2584, …。

フィボナッチ数は完全数にはならない。より一般に、フィボナッチ数は倍積完全数にもならず、2つのフィボナッチ数の商も完全数にはならない。

フィボナッチ数列の逆数和は収束し、記号 ψ}} で表される。

この ψ}} が無理数であることは証明されているが 、超越数であるかどうかは分かっていない。

任意の正の整数は、1つ以上の連続しない相異なるフィボナッチ数の和として一意に表すことができる。

5. プログラミング言語での実装
----------------

再帰的処理の例としてよく紹介される。以下はPythonでの例。

5.1. 例1
-------

def fibonacci: if n == 0 or n == 1: return n else: return fibonacci + fibonacci

5.2. 例2
-------

def fibonacci: a, b = 1, 0 for _ in range: a, b = b, a + b return b

5.3. 例3
-------

def fibonacci: return round / 2)  n -  / 2)  n) / 5  0.5) しかし、上記例1のプログラムでは n}} が与えられてから 1=//Fn//}} が求まるまでに 回の関数呼び出しが発生するため、実用的ではない。したがって通常は、例4に示すような指数関数的なコールを必要としない実装を行うか、線形時間で計算するためにメモ化などの手法を用いる。さらに、n}} が大きい場合には一般項の公式や行列表現を利用して対数時間での計算を行う。

5.3.1. 例4
---------

def fibonacci: if n > 1: return fibonacci return b

6. その他の話題
---------

フィボナッチ数は自然界の現象に数多く出現する。
また、フィボナッチ数列が生み出す螺旋は、世界で最も美しい螺旋だと言われている。 　 ヨハネス・ケプラーは1611年に発表した小論文「深淵の贈り物あるいは六角形の雪について」において、フィボナッチ数を自己を増殖する比例と呼び、植物の種子の能力の現れであると論じた。

花びらの数はフィボナッチ数であることが多い。
フィボナッチ数は、花びらの枚数も決めているらしい。
3枚：ユリ、アヤメ、エンレイソウ
5枚：オダマキ、サクラソウ、キンボウゲ、ノイバラ、ヒエンソウ
8枚：デルフィニウム属、サンギナリア、コスモス
13枚：シネラリア、コーンマリゴールド
21枚：チコリー、オオハンゴンソウ
34枚：オオバコ、シロバナムシヨケギク
55枚：ユウゼンギク
89枚：ミケルマス・デイジー
花弁の数が144に達することはない。この数は、他の自然界に見られるフィボナッチ数の例でも限界になっていることが多い。
アブラナやダイコンの花びらは4枚であり、植物学では花式図より3数性、4数性、5数性で分類される。
植物の花や実に現れる螺旋の数もフィボナッチ数であることが多い。
ヒマワリの螺旋の数はフィボナッチ数とされることもあるが、螺旋の数が多い場合、中心から離れると螺旋の隙間にも種ができてしまうため、途中から枝分かれしてフィボナッチ数にならないこともある。
パイナップルの螺旋の数は時計回りは13、反時計回りは8になっている。
葉序はフィボナッチ数と関連している。
らせん葉序におけるシンパー・ブラウンの法則はフィボナッチ数列と関連するが、「近似値を示すにすぎず、またこれにあてはまらない例もある」。
ハチやアリなど、オスに父親がない家系を辿っていくとフィボナッチ数列が現れる。
n}} 段の階段を1段または2段ずつ登るときに、登る場合の数は //F//sub 通りある。
●と○を合わせて n}} 個並べる。●が2個以上続かないように一列に並べる方法は //F//sub 通りある。
為替などのテクニカル分析で、フィボナッチ・リトレースメントという手法がよく使われている。

7. 負数番への拡張
----------

フィボナッチ数列は、漸化式 1=//Fsub を全ての整数 n}} に対して適用することにより、n}} が負の整数の場合に拡張できる。そして 1=//F//sub が成り立つ。この式より、負の番号の項は次のようになる。//



8. 類似の数列
--------

フィボナッチ数列の定義である初期値や漸化式をやや変更して、類似の数列が作れる。

8.1. 項数の変更
----------

フィボナッチ数列は各項が先行する二項の和であるものであったが、それを「先行する k}} 項の和」と置き換えた一般化

を考えることができる。ただし、初期値は 1 で埋める

あるいは 0 で埋める

などを取るのが一般的である。これらフィボナッチ数列の類似物を、項数 k}} に対応するラテン語またはギリシャ語に由来する倍数接頭辞を「フィボナッチ」と組み合わせた名称で呼ぶ当然のことだが "Fibonacci" は人名であって、"fibo-" + "-nacci" や "fi-" + "-bonacci" という構成の合成語でもないし、もちろん "fi-" や "fibo-" が "math。



8.1.1. トリボナッチ数
--------------

特に直前の三項の和として各項が定まるトリボナッチ数列は、フィボナッチ数列に次いでよく調べられている。0-fil型でオフセットが0番目からのものは

と表される。第0～21項の値は次の通りである：

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, …}} トリボナッチ数列の一般項は次で表される。

ただし、//α//, //β//, //γ//}} は三次方程式 1=//x//sup の3解

であり、ここで

である。

また、上記の α}} をトリボナッチ定数という。これはフィボナッチ数列における黄金数に当たる定数で、トリボナッチ数列の隣接2項間の商はトリボナッチ定数に収束する：

8.1.2. テトラナッチ数
--------------

直前の四項の和に変更したテトラナッチ数列も同様に様々なことが知られている。同様にオフセット0番の 0-fil型は

と書けて、第0～21項の値は次の通りである：

0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, …}} 一般項は、四次方程式 //x//sup の4解を //α//, //β//, //γ//, //δ//}} として、

となる。

8.2. 初期値の変更
-----------

8.2.1. リュカ数
-----------

フィボナッチ数列の最初の2項を 2, 1 に置き換えた数列の項をリュカ数という。

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, … この数列の一般項は

と表される。

フィボナッチ数列やリュカ数の列を一般化したものがリュカ数列であり、1878年にエドゥアール・リュカが体系的な研究を行い、1913年にロバート・ダニエル・カーマイケルがその結果を整理、拡張した。これらの研究が現代のフィボナッチ数の理論の基礎となった。

9. 脚注
-----

9.1. 注釈
-------

9.2. 出典
-------

10. 参考文献
--------

author=[[レオナルド・フィボナッチ - 『平方の書』の英訳。
last=Sigler - 『算盤の書』の英訳。

11. 関連項目
--------

黄金比
数学定数
数列
フィボナッチ数列の逆数和
リュカ数
リュカ数列

12. 外部リンク
---------

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]