フィボナッチ数

フィボナッチ数（フィボナッチすう、）は、イタリアの数学者レオナルド・フィボナッチ（ピサのレオナルド）に因んで名付けられた数である。
概要.
 は、次の漸化式で定義される：
第0～22項の値は次の通りである：
1202年にフィボナッチが発行した『算盤の書』(Liber Abaci) に記載されたことで「フィボナッチ数」と呼ばれているが、それ以前にもインドの学者であるヘーマチャンドラ (Hemachandra) が韻律の研究により発見し、書物に記したことが判明している。
兎の問題.
レオナルド・フィボナッチは次の問題を考案した。
つがいの数は次の表のようになる。どの月のつがいの合計も、その前の2つの月での合計の和となり、フィボナッチ数が現れていることが分かる。
一般項.
フィボナッチ数列の一般項は次の式で表される：
この式は1843年にビネ () が発表したことからビネの公式と呼ばれるが、それ以前の1730年（ド・モアブル）・1765年（オイラー）にも発表されており、ビネは最初の発見者ではない。
なお、この式に現れる
は黄金数で、いくつかの数学的特徴がある。黄金数を作る二次方程式 の解を とすると、上記の一般項は
と表せる。
また、一般項の第2項 formula_4 の絶対値は減少列で、 のとき formula_5 より、第2項を切り捨てた式は の値を 0.447 以下（ のとき1%以下）の誤差で与える近似式である。
この誤差の絶対値は0.5未満なので、 の正確な整数値は以下の式で得られる。
ただし、formula_8 は床関数である。
なお、後述の負数番への拡張を考慮した場合、 では逆に一般項の第1項の絶対値が0.5未満となるため、 における の正確な整数値は以下の式で得られる。
これらのことから、任意の整数 における の正確な整数値は以下の式で得られる。
ただし、 は符号関数である。
また、フィボナッチ数列の漸化式は次のように行列表現できる：
母関数は
である。
性質.
フィボナッチ数列の隣接2項の商は黄金数 に収束する。この性質は初期値 () に依らない。
これは次のように導出される：
これより以下を導くことができる。
フィボナッチ数の累和や累積について以下の式が成り立つ。
また、次の関係式が知られている。
フィボナッチ数のうち平方数であるのは , のみ (Cohn 1964)、立方数であるのは , のみ (London and Finkelstein 1969)である。フィボナッチ数のうち累乗数であるのはこれしかない (Bugeaud, Mignotte, Siksek 2006)。（）
フィボナッチ数で素数であるのは 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つのフィボナッチ数の商も完全数にはならない。
フィボナッチ数列の逆数和は収束し、記号 で表される。
この が無理数であることは証明されているが (André-Jeannin 1989)、超越数であるかどうかは分かっていない。
任意の正の整数は、1つ以上の連続しない相異なるフィボナッチ数の和として一意に表すことができる（ゼッケンドルフの定理）。
プログラミング言語での実装.
再帰的処理の例としてよく紹介される。以下はPythonでの例。
例1（再帰的処理による実装例）.
def fibonacci(n):
 if n == 0 or n == 1:
 return n
 else:
 return fibonacci(n - 2) + fibonacci(n - 1)
例2（ループ処理による実装例）.
def fibonacci(n):
 a, b = 1, 0
 for _ in range(n):
 a, b = b, a + b
 return b
例3（一般項による実装例）.
def fibonacci(n):
 return round((((1 + 5 ** 0.5) / 2) ** n - ((1 - 5 ** 0.5) / 2) ** n) / 5 ** 0.5)
しかし、上記例1のプログラムでは が与えられてから が求まるまでに formula_20 回の関数呼び出しが発生する（すなわち指数時間の計算となる）ため、実用的ではない。したがって通常は、例4に示すような指数関数的なコールを必要としない実装を行うか、線形時間で計算するためにメモ化などの手法を用いる。さらに、 が大きい場合には一般項の公式（上記例3）や行列表現を利用してでの計算を行う。
例4（指数関数的なコールを必要としない再帰的処理による実装例）.
def fibonacci(n, a = 0, b = 1):
 if n > 1:
 return fibonacci(n - 1, b, a + b)
 return b
その他の話題.
　ヨハネス・ケプラーは1611年に発表した小論文「深淵の贈り物あるいは六角形の雪について」において、フィボナッチ数を自己を増殖する比例と呼び、植物の種子の能力の現れであると論じた。
負数番への拡張.
フィボナッチ数列は、漸化式 を全ての整数 に対して適用することにより、 が負の整数の場合に拡張できる。そして が成り立つ。この式より、負の番号の項は次のようになる。
類似の数列.
フィボナッチ数列の定義である初期値や漸化式をやや変更して、類似の数列が作れる。
項数の変更.
フィボナッチ数列は各項が先行する二項の和であるものであったが、それを「先行する 項の和」と置き換えた一般化
を考えることができる。ただし、初期値は 1 で埋める（1-fil型）
あるいは 0 で埋める（0-fil型）
などを取るのが一般的である。これらフィボナッチ数列の類似物を、項数 に対応するラテン語またはギリシャ語に由来する倍数接頭辞を「フィボナッチ」と組み合わせた名称で呼ぶ。
トリボナッチ数.
特に直前の三項の和として各項が定まるトリボナッチ数列は、フィボナッチ数列に次いでよく調べられている。0-fil型でオフセットが0番目からのものは
と表される。第0～21項の値は次の通りである：
トリボナッチ数列の一般項は次で表される。
ただし、 は三次方程式 の3解
であり、ここで
である。
また、上記の をトリボナッチ定数という。これはフィボナッチ数列における黄金数に当たる定数で、トリボナッチ数列の隣接2項間の商はトリボナッチ定数に収束する：
テトラナッチ数.
直前の四項の和に変更したテトラナッチ数列も同様に様々なことが知られている。同様にオフセット0番の 0-fil型は
と書けて、第0～21項の値は次の通りである：
一般項は、四次方程式 の4解を として、
となる。
初期値の変更.
リュカ数.
フィボナッチ数列の最初の2項を 2, 1 に置き換えた数列の項をリュカ数という。
この数列の一般項は
と表される。
フィボナッチ数列やリュカ数の列を一般化したものがリュカ数列であり、1878年にエドゥアール・リュカが体系的な研究を行い、1913年にがその結果を整理、拡張した。これらの研究が現代のフィボナッチ数の理論の基礎となった。