フィボナッチ数列は、ピサのレオナルドにちなんで名付けられた、数学における代表的な数列の一つです。フィボナッチは1202年にLiber Abaci（「計算の書」）を著し、すでにインドの数学者が知っていた規則を西ヨーロッパに紹介しました。以降、フィボナッチ数列は数学だけでなく自然や芸術、工学にも多くの応用・出現例が見られます。

定義と基本例

フィボナッチ数列は次のような再帰関係で定義されます。すなわち、各項は直前の2項の和です。

再帰関係： Fn = Fn−1 + Fn−2。{\displaystyle F_{n}=F_{n-1}+F_{n-2}}

これを決定するために初期条件が必要で、よく用いられる定義は次の通りです。{\displaystyle F_{0}=0} and {\displaystyle F_{1}=1}

この定義により数列は次のようになります：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

生成方法（計算の仕方）

  • 反復（イテレーティブ）法：最も単純で効率的。F0, F1 から順に繰り返し計算することで O(n) 時間で Fn を得られます。
  • 再帰（単純再帰）：定義通りに再帰関数で実装すると理解は容易ですが、重複計算が多く非効率で O(φ^n) 程度かかります（φ は黄金比）。メモ化（動的計画法）で O(n) に改善できます。
  • 行列累乗法：行列 [[1,1],[1,0]] の n 乗を使うと高速に計算でき、二分累乗を用いれば O(log n) の時間で Fn を求められます。
  • 高速倍増法（fast doubling）：再帰的に二乗法の考えで Fn を直接求める方法で、これも O(log n) で計算できます。大きな n を扱う場合に実用的です。
  • 閉形式（ビネの公式）：φ = (1+√5)/2 として
    Fn = (φ^n − (1−φ)^n) / √5。実数近似や理論的解析に便利ですが、大きな n の整数値を直接得るには丸め誤差に注意が必要です。

主な性質と恒等式

  • 漸近的比率（黄金比）：隣接する項の比 Fn+1/Fn は n→∞ で φ = (1+√5)/2 ≈ 1.618... に収束します。
  • 和に関する公式：初項から n 項目までの和は F0 + F1 + ... + Fn = Fn+2 − 1 です。
  • カッシーニの恒等式：Fn+1Fn−1 − Fn^2 = (−1)^n。整数恒等式の一例です。
  • 行列表現：[[Fn+1, Fn],[Fn, Fn−1]] = [[1,1],[1,0]]^n。
  • モジュロ周期（ピサノ周期）：任意の正整数 m に対し、Fn を m で割った余りは周期性を持ちます（これをピサノ周期と呼ぶ）。

応用例と出現場所

フィボナッチ数列は次のような分野で現れます：

  • 生物学：花弁の数や種子の配列（ヒマワリの種の螺旋）、貝殻の螺旋の近似など。
  • 芸術・建築：黄金比に基づく比率や構図。
  • アルゴリズム：フィボナッチヒープや斐波那契探索（古い手法）など。
  • 暗号や数論：フィボナッチ数の合同算術や周期性の研究。

計算上の注意

  • 大きな n を求めるときは、単純再帰は避け、行列累乗や高速倍増法を使うこと。整数演算が必要ならば丸め誤差のない整数アルゴリズムを選ぶ。
  • ビネの公式は理論的に便利ですが、浮動小数点での直接計算は誤差を生じやすく、整数を正確に得るためには丸めの工夫が必要です。

フィボナッチ数列は単純な定義ながら豊かな構造と多様な応用を持ち、数学の入門から研究まで幅広く登場します。興味があれば、行列を使った導出やピサノ周期、フィボナッチ数に関連する素数（フィボナッチ素数）など、さらに深い話題に進んでみてください。