フィボナッチ数

ファイル:34*21-FibonacciBlocks.png

フィボナッチ数列の各項を一辺とする正方形

ファイル:Image from Gutza Wikipedia.jpg

ウィキペディア日本語版のメインページ（2007年〜2012年）で使われていたイメージ画像もフィボナッチ数列を利用している

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

概要

n 番目のフィボナッチ数を F_n で表すと、F_n は再帰的に

F₀ = 0,

F₁ = 1,

F_{n + 2} = F_n + F_{n + 1} (n ≧ 0)

で定義される。これは、2つの初期条件を持つ漸化式である。

この数列 (F_n)はフィボナッチ数列（フィボナッチすうれつ、Fibonacci sequence）と呼ばれ、

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …（オンライン整数列大辞典の数列 A45）

と続く。最初の二項は 0, 1 であり、以後どの項もその直前の2つの項の和となっている。

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

兎の問題

フィボナッチは次の問題を考案した。

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

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

	産まれたばかりのつがい	生後1か月のつがい	生後2か月以降のつがい	つがいの数（合計）
0か月後	1	0	0	1
1か月後	0	1	0	1
2か月後	1	0	1	2
3か月後	1	1	1	3
4か月後	2	1	2	5
5か月後	3	2	3	8
6か月後	5	3	5	13
7か月後	8	5	8	21
8か月後	13	8	13	34
9か月後	21	13	21	55
10か月後	34	21	34	89
11か月後	55	34	55	144
12か月後	89	55	89	233

一般項

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

[math]F_n = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\} = {{\phi^n - (1-\phi)^n} \over \sqrt{5}} = {{\phi^n - (-\phi)^{-n}} \over \sqrt{5}}.[/math]

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

なおこの式に現れる、

[math]\phi = \frac{1+\sqrt{5}}{2} \approx 1.618 033 988 749 895[/math]

という値は、黄金比という別名がある値で、いくつかの（しばしば数秘術的な信仰者が見られる）特徴がある。

この式の第2項は n = 0 のときの [math]1 / \sqrt{5} \approx 0.447[/math] が最大で、それを超えることはない。従って、第2項を略した次の式は F_n の値を 0.447 以下（n > 4 のとき1%以下）の誤差で与える近似式である。

[math]F_n \approx {\phi^n \over \sqrt{5}}.[/math]

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

[math]F_n = \left\lfloor {\phi^n \over \sqrt{5}} + \frac{1}{2} \right\rfloor.[/math]

ただし、[math]\lfloor x\rfloor[/math] は床関数である。 フィボナッチ数列の漸化式は次のように行列表現できる:

[math]{F_{n + 2} \choose F_{n + 1}} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} {F_{n + 1} \choose F_n}[/math]
ゆえに [math]\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n[/math]

性質

隣り合うフィボナッチ数の比は黄金比 φ に収束する。この性質は初期値 (F₀ = 0, F₁ = 1) に依らない。

[math]\lim_{n \to \infty} {F_n \over F_{n-1}} = \phi.[/math]

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

[math]x = \lim_{n \to \infty}{F_n \over F_{n-1}}[/math] が収束するとすれば、
[math]x = \lim_{n \to \infty} \frac{F_{n-1} + F_{n-2}}{F_{n-1}} = \lim_{n \to \infin} \left( 1 + \frac{1}{ F_{n-1} / F_{n-2} } \right) = 1 + \frac{1}{x}[/math]
[math]x^2-x-1=0\,[/math]

2つの自然数 p と q の最大公約数が r であるならば F_p と F_q の最大公約数は F_r である。 このことより以下を導くことができる。

• m が n で割り切れるならば、F_m は F_n で割り切れる。
• 連続する2数は互いに素であることより、隣り合うフィボナッチ数も互いに素である。

F_m が偶数となるのは m が 3 の倍数となるときと一致する。 F_m が 5 の倍数となるのは m が 5 の倍数となるときと一致する。 p が 2 でも 5 でもない素数のとき、m = p − (5/p) とおくと p は F_m を割り切る。ここで ( / ) はルジャンドル記号である。

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

• F₁ + F₂ + F₃ + ⋯ + F_n = F_{n + 2} − 1
• F₁ + F₃ + F₅ + ⋯ + F_{2n − 1} = F_2n
• F₂ + F₄ + F₆ + ⋯ + F_2n = F_{2n + 1} − 1
• F₁² + F₂² + F₃² + ⋯ + F_n² = F_n F_{n + 1}
• F_{n − 1} F_{n + 1} − F_n² = (− 1)ⁿ

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

[math]\frac{1}{89}=\sum_{n=1}^\infty{F_n\times 10^{-(n+1)}}.[/math]

フィボナッチ数のうち平方数であるものは F₁ = F₂ = 1, F₁₂ = 144 のみ (Cohn 1964)、立方数であるものは F₁ = F₂ = 1, F₆ = 8 のみ (London and Finkelstein 1969) である。フィボナッチ数のうち累乗数であるものはこれしかない (Bugeaud, Mignotte, Siksek 2006)。(オンライン整数列大辞典の数列 A227875)

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

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

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

フィボナッチ数の逆数の総和はある一定の値に収束し、記号 ψ で表される。

[math]\psi = \sum_{n = 1}^\infty \frac{1}{F_n} = \frac{1}{1} + \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots \approx 3.35988566 \ldots[/math]

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

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

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

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

#include <stdio.h>

int fibonacci(int n)
{
    switch (n) {
        case 0: return 0;
        case 1: return 1;
        default: return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

int main(void)
{
    int n;
    printf("n = ");
    scanf("%d", &n);
    printf("F(%d) = %d\n", n, fibonacci(n));
    return 0;
}

しかし、上記のプログラムでは n が与えられてから F_n が求まるまでに [math]F_n \propto \phi^n[/math] 回の関数呼び出しが発生する（すなわち指数時間の計算となる）ため、実用的ではない。したがって通常は、線形時間で計算するためにメモ化などの手法を用いる。さらに、n が大きい場合には一般項の公式や行列表現を利用して対数時間での計算を行う。

その他の話題

ファイル:Helianthus whorl.jpg

ヒマワリの種は螺旋状に並んでおり、螺旋の数を数えていくとフィボナッチ数が現れる

• フィボナッチ数は自然界の現象に数多く出現する。
  • 花びらの数はフィボナッチ数であることが多い。
  • 植物の花や実に現れる螺旋の数もフィボナッチ数であることが多い。
    • ヒマワリの螺旋の数はフィボナッチ数とされることもあるが、螺旋の数が多い場合、中心から離れると螺旋の隙間にも種ができてしまうため、途中から枝分かれしてフィボナッチ数にならないこともある。
  • パイナップルの螺旋の数は時計回りは13、反時計回りは8になっている。
  • 葉序（植物の葉の付き方）はフィボナッチ数と関連している。
  • ハチやアリなど、オスに父親がない家系を辿っていくとフィボナッチ数列が現れる（父母2匹、祖父母3匹、曽祖父母5匹、高祖父母8匹…）。
• n 段の階段を1段または2段ずつ登るときに、登る場合の数は F_{n + 1} 通りある。
• ●と○を合わせて n 個並べる。●が2個以上続かないように一列に並べる方法は F_{n + 2} 通りある。
• 為替などのテクニカル分析で、フィボナッチ・リトレースメントという手法がよく使われている。

負数番への拡張

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

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	F18	F19	F20
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765
F0	F−1	F−2	F−3	F−4	F−5	F−6	F−7	F−8	F−9	F−10	F−11	F−12	F−13	F−14	F−15	F−16	F−17	F−18	F−19	F−20
0	1	−1	2	−3	5	−8	13	−21	34	−55	89	−144	233	−377	610	−987	1597	−2584	4181	−6765

類似の数列

フィボナッチ数列を与える漸化式をやや変更して、初期値や漸化式の項数を変えた類似の数列が作れる。

項数の変更

フィボナッチ数列は各項が先行する二項の和になるものであったから、それを「先行する k 項の和」と置き換えた一般化[math]F_{n+k}^{(k)} := F_{n+k-1}^{(k)} + F_{n+k-2}^{(k)} + \dotsb + F_n^{(k)}\quad(\forall n\ge 0)[/math]を考えることができる。ただし、初期値は 1 で埋める (1-fil型) [math]F_0^{(k)} = F_1^{(k)}=\dotsb=F_{k-1}^{(k)}=1[/math]あるいは 0 で埋める (0-fil型) [math]F_0^{(k)} = F_1^{(k)}=\dotsb=F_{k-2}^{(k)}=0,\quad F_{k-1}^{(k)}=1[/math]などを取るのが一般的である。これらフィボナッチ数列の類似物を、項数 k に対応するラテン語またはギリシャ語に由来する倍数接頭辞を「フィボナッチ」と組み合わせた名称で呼ぶ。

和の項数や初期値の変更

k	接頭辞	名称	整数列大辞典
3	tri-	トリボナッチ数	0 fil: テンプレート:OEIS2C 1 fil: テンプレート:OEIS2C
4	tetra-	テトラナッチ数	0 fil: テンプレート:OEIS2C 1 fil: テンプレート:OEIS2C
5	penta-	ペンタナッチ数	0 fil: テンプレート:OEIS2C 1 fil: テンプレート:OEIS2C
6	hexa-	ヘキサナッチ数	0 fil: テンプレート:OEIS2C 1 fil: テンプレート:OEIS2C
7	hepta-	ヘプタナッチ数	0 fil: テンプレート:OEIS2C 1 fil: テンプレート:OEIS2C
8	octa-	オクタナッチ数	0 fil: テンプレート:OEIS2C 1 fil: テンプレート:OEIS2C
9	nona-	ノナ（ボ）ナッチ数	0 fil: テンプレート:OEIS2C 1 fil: テンプレート:OEIS2C
10	deca-	デカ（ボ）ナッチ数	1 fil: テンプレート:OEIS2C
11	undeca-	ウンデカ（ボ）ナッチ数	1 fil: テンプレート:OEIS2C
12	dodeca-	ドデカ（ボ）ナッチ数	1 fil: テンプレート:OEIS2C
⋮
20	icosa-
⋮

トリボナッチ数

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

T₀ = T₁ = 0, T₂ = 1,

T_{n + 3} = T_n + T_{n + 1} + T_{n + 2} (n ≥ 0).

のように書ける。この最初のいくつかの項は、次のようになる:

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … (OEIS テンプレート:OEIS2C).

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

[math]T_n = \frac{\alpha^n}{(\alpha - \beta)(\alpha - \gamma)}+ \frac{\beta^n}{(\beta - \gamma)(\beta - \alpha)}+ \frac{\gamma^n}{(\gamma - \alpha)(\gamma - \beta)}.[/math]

ただし、α, β, γ は三次多項式 x³ − x² − x − 1 の三根

[math]\begin{align} \alpha &= \frac{1}{3} \left(1 + \sqrt[3]{19-3\sqrt{33}} + \sqrt[3]{19+3\sqrt{33}}\right) \\ \beta &= \frac{1}{3} \left(1 + \omega \sqrt[3]{19-3\sqrt{33}} + \bar{\omega} \sqrt[3]{19+3\sqrt{33}}\right) \\ \gamma &= \frac{1}{3} \left(1 + \bar{\omega} \sqrt[3]{19-3\sqrt{33}} + \omega \sqrt[3]{19+3\sqrt{33}}\right) \end{align}[/math]

であり、ここに

[math]\omega = \frac{- 1 + \sqrt{3} i}{2}[/math]

は 1 の虚立方根である。

また、上の3つの根のうち、実数解 α のことをトリボナッチ定数という。これはフィボナッチ数列の黄金比にあたる定数で、トリボナッチ数列の隣り合う2項間の比は、トリボナッチ定数に収束する:

[math]\lim_{n \to \infin} {T_n \over T_{n - 1}} = \alpha \approx 1.839286755214162.[/math]

テトラナッチ数

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

T₀ = T₁ = T₂ = 0, T₃ = 1,

T_{n + 4} = T_n + T_{n + 1} + T_{n + 2} + T_{n + 3}　　(n ≥ 0).

と書けて、最初のいくつかの項は、次のようになる:

0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, … (OEIS テンプレート:OEIS2C).

一般項は、四次多項式 [math]x^4-x^3-x^2-x-1[/math] の四つの根を α, β, γ, δ として、

[math]T_n = \frac{\alpha^n}{(\alpha- \beta)(\alpha - \gamma)(\alpha - \delta)}+ \frac{\beta^n}{(\beta - \gamma)(\beta - \delta)(\beta - \alpha)}+ \frac{\gamma^n}{(\gamma - \delta)(\gamma - \alpha)(\gamma - \beta)}+ \frac{\delta^n}{(\delta - \alpha)(\delta - \beta)(\delta - \gamma)}[/math]

のようになる。

初期値の変更

リュカ数

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

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, … テンプレート:OEIS2C

この数列の一般項は

[math]L_n = \left( \frac{1+\sqrt{5}}{2} \right)^n + \left( \frac{1-\sqrt{5}}{2} \right)^n= \phi^n + (1-\phi)^n = {\phi^n + (-\phi)^{-n}}[/math]

と表される。

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

参考文献

• 佐藤修一 『自然にひそむ数学　自然と数学の不思議な関係』 講談社〈ブルーバックス B-1201〉、1998-01-20。ISBN 4-06-257201-X。
• 中村滋 『フィボナッチ数の小宇宙（ミクロコスモス）　フィボナッチ数、リュカ数、黄金分割』 日本評論社、1993年。ISBN 4-535-78281-4。
  • 中村滋 『フィボナッチ数の小宇宙（ミクロコスモス）　フィボナッチ数、リュカ数、黄金分割』 日本評論社、2007年、改訂版。ISBN 978-4-535-78492-5。
• Arakelian, Hrant (2014) (ロシア語), Mathematics and History of the Golden Section, Logos, ISBN 978-5-98704-663-0 
• Dunlap, Richard A. (1997-12-17), The Golden Ratio and Fibonacci Numbers, World Scientific Pub. Co. Inc., ISBN 978-981-02-3264-1 
  • ダンラップ, R.A. 『黄金比とフィボナッチ数』 岩永恭雄・松井講介訳、日本評論社、2003-06。ISBN 4-535-78370-5。
• Koshy, Thomas (2017-12-04), Fibonacci and Lucas Numbers with Applications, Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts (Book 1), 1st volume, Wiley, ISBN 978-1-118-74212-9 
• Leonardo Pisano Fibonacci L. E. Sigler訳 (1987-02-11), The Book of Squares, Academic Press, ISBN 978-0-12-643130-8  - 『平方の書』の英訳。
• Sigler, Laurence (2003-11-11), Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation, Sources and Studies in the History of Mathematics and Physical Sciences, Springer-Verlag, ISBN 978-0-387-40737-1  - 『算盤の書』の英訳。

関連項目

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

外部リンク

• テンプレート:高校数学の美しい物語
• Weisstein, Eric W. “Fibonacci Number”. MathWorld（英語）.
• The Fibonacci Association（フィボナッチ協会）（英語）
• Fibonacci Quarterly Home Page（フィボナッチ・クォータリー）（英語）