Remove ads

フィボナッチ数(フィボナッチすう、: Fibonacci number)は、イタリアの数学者レオナルド・フィボナッチ(ピサのレオナルド)に因んで名付けられたである。

Thumb
フィボナッチ数を一辺とする正方形
Remove ads

概要

フィボナッチ数列フィボナッチすうれつ: Fibonacci sequence (Fn) は、次の漸化式で定義される:

第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, …(オンライン整数列大辞典の数列 A000045

1202年にフィボナッチが発行した『算盤の書』(Liber Abaci) に記載されたことで「フィボナッチ数」と呼ばれているが、それ以前にもインドの学者であるヘーマチャンドラ (Hemachandra) が韻律の研究により発見し、書物に記したことが判明している[1][2]

Remove ads

兎の問題

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

  • 1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む。
  • 兎が死ぬことはない。
  • この条件の下で、産まれたばかりの1つがいの兎は1年の間に何つがいの兎になるか?

つがいの数は次の表のようになる。どの月のつがいの合計も、その前の2つの月での合計の和となり、フィボナッチ数が現れていることが分かる。

さらに見る 産まれたばかりのつがい, 生後1か月のつがい ...
産まれたばかりのつがい生後1か月のつがい生後2か月以降のつがいつがいの数(合計)
0か月後 1001
1か月後 0101
2か月後 1012
3か月後 1113
4か月後 2125
5か月後 3238
6か月後 53513
7か月後 85821
8か月後 1381334
9か月後 21132155
10か月後 34213489
11か月後 553455144
12か月後 895589233
閉じる
Remove ads

一般項

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

この式は1843年ビネ (Jacques Philippe Marie Binet) が発表したことからビネの公式と呼ばれるが、それ以前の1730年ド・モアブル)・1765年オイラー)にも発表されており、ビネは最初の発見者ではない。

なお、この式に現れる

黄金数で、いくつかの数学的特徴がある。黄金数を作る二次方程式 x2 x 1 = 0 の解を α, β (α > β) とすると、上記の一般項は

と表せる。

また、一般項の第2項 1/ 5 (φ)n の絶対値は減少列で、n = 0 のとき 1/ 5 = 0.447... < 1/2 より、第2項を切り捨てた式は Fn の値を 0.447 以下(n > 4 のとき1%以下)の誤差で与える近似式である。

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

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

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

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

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

行列表現

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

これらを並べて表記すると、

ここで、F1 = 1 は、漸化式 Fn = Fn1 + Fn2n = 1 を代入すると得られる(詳細は後述の負数番への拡張を参照)。

更に、n2n で置換すると、

よって、

母関数

である。

また、この行列表現を基に、以下のような漸化式を考えることができる。

Remove ads

性質

フィボナッチ数列の隣接2項の商は黄金数 φ に収束する。この性質は初期値 (F0 = 0, F1 = 1) に依らない。

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

が収束するとすれば、
  • 自然数 p, q最大公約数r とすると、FpFq の最大公約数は Fr である。

これより以下を導くことができる。

  • mn で割り切れるならば、FmFn で割り切れる。
  • 連続する2数は互いに素であることより、隣り合うフィボナッチ数も互いに素である。
  • Fm偶数となるのは m が 3 の倍数となるときと一致する。
  • Fm が 5 の倍数となるのは m が 5 の倍数となるときと一致する。
  • p が 2 でも 5 でもない素数のとき、m = p (5/p) とおくと pFm を割り切る。ここで ( / )ルジャンドル記号である。

フィボナッチ数の累和や累積について以下の式が成り立つ。

  • F1 + F2 + F3 + … + Fn = Fn+2 1
  • F1 + F3 + F5 + … + F2n1 = F2n
  • F2 + F4 + F6 + … + F2n = F2n+1 1
  • F12 + F22 + F32 + … + Fn2 = Fn Fn+1
  • Fn1 Fn+1 Fn2 = (1)n

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

フィボナッチ数のうち平方数であるのは F1 = F2 = 1, F12 = 144 のみ (Cohn 1964)[4]立方数であるのは F1 = F2 = 1, F6 = 8 のみ (London and Finkelstein 1969)[5]である。フィボナッチ数のうち累乗数であるのはこれしかない (Bugeaud, Mignotte, Siksek 2006)[6]。(オンライン整数列大辞典の数列 A227875

フィボナッチ数で素数であるのは 2, 3, 5, 13, 89, 233, 1597, 28657, … である(オンライン整数列大辞典の数列 A005478)。また、これらはフィボナッチ素数と呼ばれる。

フィボナッチ数で三角数であるのは 1, 3, 21, 55オンライン整数列大辞典の数列 A039595)のみであることは Vern Hoggatt によって予想されていたが、のちに Luo Ming によって証明された[7]

フィボナッチ数でハーシャッド数であるのは 1, 2, 3, 5, 8, 21, 144, 2584, …(オンライン整数列大辞典の数列 A117774)。

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

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

[11]

この ψ が無理数であることは証明されているが (André-Jeannin 1989)、超越数であるかどうかは分かっていない。

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

Remove ads

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

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

ただし、下記実装例の内、#負数番への拡張に対応しているのは例5・例6のみである。

例1(再帰的処理による実装例)

このプログラムでは、n が与えられてから Fn が求まるまでに Fnφn 回の関数呼び出しが発生する(すなわち指数時間の計算となる)ため、実用的ではない。したがって通常は、線形時間で計算するためにメモ化などの手法を用いる他、後述するように様々な実装例が検討されている。

def fib(n: int) -> int:
    if n < 2:
        return n
    else:
        return fib(n=n-1) + fib(n=n-2)

メモ化の例を挙げると[注釈 1]

from functools import cache

@cache
def fib(n: int) -> int:
    if n < 2:
        return n
    else:
        return fib(n=n-1) + fib(n=n-2)

例2(ループ処理による実装例)

def fib(n: int) -> int:
    a, b = 1, 0
    for _ in range(n):
        a, b = b, a+b
    return b

例3(指数関数的なコールを必要としない再帰的処理による実装例)

n が1以上の場合に第2・第3の引数を上記例2と同じ要領で順次更新していくことで、コール回数を n 回に抑えられる為、線形時間で処理できる。

def fib(n: int, a: int = 1, b: int = 0) -> int:
    if n == 0:
        return b
    else:
        return fib(n=n-1, a=b, b=a+b)

例4(対数時間での再帰的処理による実装例)

#行列表現で導出した漸化式(以下に再掲)を用いることで、再帰的処理でも対数時間で処理できる。

ただし、プログラム上は0を掛けるからと言ってその対象の値が計算されない訳では無い為(短絡評価されない)、条件式による分岐で表記している。

def fib(n: int) -> int:
    if n < 2:
        return n
    q = n // 2
    fq = fib(n=q)
    return fq ** 2 + (2 * fib(n=q-1) * fq if n % 2 == 0 else fib(n=q+1) ** 2)

例5(一般項による実装例)

浮動小数点型を使用すると計算誤差が発生する為、decimalモジュールを用いている[注釈 2]

from decimal import Decimal

SQRT5 = Decimal(5).sqrt()
PHI = (1 + SQRT5) / 2 # 黄金数

def fib(n: int) -> int:
    return round((PHI ** n - (-PHI) ** -n) / SQRT5)

なお、先述の通りフィボナッチ数列の一般項は、引数 n の符号によって2項の内いずれかが0.5未満となることから、符号関数及び床関数を用いて以下のように表すことができた。

#一般項より再掲)

このことから、以下のように実装することで冪乗演算の回数を減らすことが出来る[注釈 3]

from decimal import Decimal

ONE = Decimal(1)
SQRT5 = Decimal(5).sqrt()
PHI = (1 + SQRT5) / 2 # 黄金数

def fib(n: int) -> int:
    if n == 0:
        return 0
    sgn_n = ONE.copy_sign(n)
    return sgn_n * round((sgn_n * PHI) ** abs(n) / SQRT5)

例6(行列表現での実装例)

#行列表現より再掲)

より、nn 1 に置換すると、

従って、Fn は、上式右辺(の具体的な計算値)の左上成分に等しい。

行列の冪を簡潔に記述する為にSymPyを用いた[注釈 4][注釈 5]。 {{Syntaxhighlight|lang=python|code= from sympy import Matrix

def fib(n: int) -> int:

   return (Matrix([[1, 1], [1, 0]]) ** (n - 1))[0, 0] # 左上成分

}}

Remove ads

その他の話題

Thumb
ヒマワリの種は螺旋状に並んでおり、螺旋の数を数えていくとフィボナッチ数が現れる[12]
  • フィボナッチ数は自然界の現象に数多く出現する。
  • また、フィボナッチ数列が生み出す螺旋は、世界で最も美しい螺旋だと言われている。

ヨハネス・ケプラーは1611年に発表した小論文「新年の贈り物あるいは六角形の雪について」において、フィボナッチ数を自己を増殖する比例と呼び、植物の種子の能力の現れであると論じた[13]

  • アブラナダイコン花びらは4枚であり、植物学では花式図より3数性、4数性、5数性で分類される[15][16]
  • 植物に現れる螺旋の数もフィボナッチ数であることが多い。
    • ヒマワリの螺旋の数はフィボナッチ数とされることもあるが、螺旋の数が多い場合、中心から離れると螺旋の隙間にも種ができてしまうため、途中から枝分かれしてフィボナッチ数にならないこともある[17]
  • パイナップルの螺旋の数は時計回りは13、反時計回りは8になっている。
  • 葉序(植物の葉の付き方)はフィボナッチ数と関連している。(シンパー=ブラウンの法則)
  • らせん葉序におけるシンパー・ブラウンの法則はフィボナッチ数列と関連するが、「近似値を示すにすぎず、またこれにあてはまらない例もある」(岩波生物学辞典)。
  • ハチアリなど、オスに父親がない家系を辿っていくとフィボナッチ数列が現れる(父母2匹、祖父母3匹、曽祖父母5匹、高祖父母8匹…)。
  • n 段の階段を1段または2段ずつ登るときに、登る場合の数は Fn+1 通りある。
  • ●と○を合わせて n 個並べる。●が2個以上続かないように一列に並べる方法は Fn+2 通りある。
  • 為替などのテクニカル分析で、フィボナッチ・リトレースメントという手法がよく使われている。
Remove ads

負数番への拡張

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

さらに見る n, Fn ...
n 01234567891011121314151617181920
Fn 011235813213455891442333776109871597258441816765
Fn 011235813213455891442333776109871597258441816765
閉じる
Remove ads

類似の数列

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

項数の変更

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

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

あるいは 0 で埋める(0-fil型)

などを取るのが一般的である。これらフィボナッチ数列の類似物を、項数 k に対応するラテン語またはギリシャ語に由来する倍数接頭辞を「フィボナッチ」と組み合わせた名称で呼ぶ[注釈 6]

さらに見る k, 接頭辞 ...
和の項数や初期値の変更
k接頭辞[18]名称整数列大辞典
3tri- トリボナッチ数 0 fil: A000073
1 fil: A000213
4tetra- テトラナッチ数 0 fil: A000078
1 fil: A000288
5penta- ペンタナッチ数 0 fil: A001591
1 fil: A000322
6hexa- ヘキサナッチ数 0 fil: A001592
1 fil: A000383
7hepta- ヘプタナッチ数 0 fil: A122189
1 fil: A060455
8octa- オクタナッチ数 0 fil: A079262
1 fil: A123526
9nona- ノナ(ボ)ナッチ数 1 fil: A127193
10deca- デカ(ボ)ナッチ数 1 fil: A127194
11undeca- ウンデカ(ボ)ナッチ数 1 fil: A127624
12dodeca- ドデカ(ボ)ナッチ数 1 fil: A207539
20icosa- イコサナッチ数
閉じる

トリボナッチ数

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

T0 = T1 = 0, T2 = 1,
Tn+3 = Tn + Tn+1 + Tn+2 (n ≥ 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, … (OEIS A000073)

トリボナッチ数列の一般項は次で表される。

ただし、α, β, γ三次方程式 x3 x2 x 1 = 0 の3解

であり、ここで

1 の虚立方根

である。

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

テトラナッチ数

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

T0 = T1 = T2 = 0, T3 = 1,
Tn+4 = Tn + Tn+1 + Tn+2 + Tn+3 (n 0)

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

0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, … (OEIS A000078)

一般項は、四次方程式 x4 x3 x2 x 1 = 0 の4解を α, β, γ, δ として、

となる。

初期値の変更

リュカ数

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

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, … (OEIS A000032)

この数列の一般項は

と表される。

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

脚注

参考文献

関連項目

外部リンク

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Remove ads