フィボナッチ数
フィボナッチ数(フィボナッチすう、英: Fibonacci number)は、イタリアの数学者レオナルド・フィボナッチ(ピサのレオナルド)にちなんで名付けられた数である。
Contents
概要
n 番目のフィボナッチ数を Fn で表すと、Fn は再帰的に
- F0 = 0,
- F1 = 1,
- Fn + 2 = Fn + Fn + 1 (n ≧ 0)
で定義される。これは、2つの初期条件を持つ漸化式である。
この数列 (Fn)はフィボナッチ数列(フィボナッチすうれつ、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]。
兎の問題
フィボナッチは次の問題を考案した[3]。
- 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 |
一般項
フィボナッチ数列の一般項は次の式で表される[3]:
- [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項を略した次の式は Fn の値を 0.447 以下(n > 4 のとき1%以下)の誤差で与える近似式である。
- [math]F_n \approx {\phi^n \over \sqrt{5}}.[/math]
この誤差は ±0.5 未満なので、Fn の正確な整数値は以下の式で得られる[3]。
- [math]F_n = \left\lfloor {\phi^n \over \sqrt{5}} + \frac{1}{2} \right\rfloor.[/math]
ただし、[math]\lfloor x\rfloor[/math] は床関数である。 フィボナッチ数列の漸化式は次のように行列表現できる[3]:
[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]
性質
隣り合うフィボナッチ数の比は黄金比 φ に収束する。この性質は初期値 (F0 = 0, F1 = 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 であるならば Fp と Fq の最大公約数は Fr である。 このことより以下を導くことができる。
- m が n で割り切れるならば、Fm は Fn で割り切れる。
- 連続する2数は互いに素であることより、隣り合うフィボナッチ数も互いに素である。
Fm が偶数となるのは m が 3 の倍数となるときと一致する。 Fm が 5 の倍数となるのは m が 5 の倍数となるときと一致する。 p が 2 でも 5 でもない素数のとき、m = p − (5/p) とおくと p は Fm を割り切る。ここで ( / ) はルジャンドル記号である。
フィボナッチ数の累和や累積について以下の式が成り立つ。
- F1 + F2 + F3 + ⋯ + Fn = Fn + 2 − 1
- F1 + F3 + F5 + ⋯ + F2n − 1 = F2n
- F2 + F4 + F6 + ⋯ + F2n = F2n + 1 − 1
- F12 + F22 + F32 + ⋯ + Fn2 = Fn Fn + 1
- Fn − 1 Fn + 1 − Fn2 = (− 1)n
また、次の関係式が知られている。
- [math]\frac{1}{89}=\sum_{n=1}^\infty{F_n\times 10^{-(n+1)}}.[/math]
フィボナッチ数のうち平方数であるものは 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)。
フィボナッチ数の逆数の総和はある一定の値に収束し、記号 ψ で表される。
[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] [8]
この ψ が無理数であることは証明されているが (André-Jeannin 1989)、超越数であるかどうかは分かっていない。
任意の正の整数は、1つ以上の連続しない相異なるフィボナッチ数の和として一意に表すことができる(ゼッケンドルフの定理)。
プログラミング言語での実装
#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 が与えられてから Fn が求まるまでに [math]F_n \propto \phi^n[/math] 回の関数呼び出しが発生する(すなわち指数時間の計算となる)ため、実用的ではない。したがって通常は、線形時間で計算するためにメモ化などの手法を用いる。さらに、n が大きい場合には一般項の公式や行列表現[3]を利用して対数時間での計算を行う。
その他の話題
- フィボナッチ数は自然界の現象に数多く出現する。
- n 段の階段を1段または2段ずつ登るときに、登る場合の数は Fn + 1 通りある。
- ●と○を合わせて n 個並べる。●が2個以上続かないように一列に並べる方法は Fn + 2 通りある。
- 為替などのテクニカル分析で、フィボナッチ・リトレースメントという手法がよく使われている。
負数番への拡張
フィボナッチ数列は、漸化式 Fn = Fn − 1 + Fn − 2 を全ての整数 n に対して適用することにより、n が負の整数の場合に拡張できる。そして F−n = (−1)n + 1Fn が成り立つ。この式より、負の番号に対する数項は次のようになる。
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 に対応するラテン語またはギリシャ語に由来する倍数接頭辞を「フィボナッチ」と組み合わせた名称で呼ぶ[注釈 1]。
k | 接頭辞[11] | 名称 | 整数列大辞典 |
---|---|---|---|
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番目からのものは
- T0 = T1 = 0, T2 = 1,
- Tn + 3 = Tn + Tn + 1 + Tn + 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]
ただし、α, β, γ は三次多項式 x3 − x2 − 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型は
- T0 = T1 = T2 = 0, T3 = 1,
- Tn + 4 = Tn + Tn + 1 + Tn + 2 + Tn + 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年にロバート・ダニエル・カーマイケルがその結果を整理、拡張した[12]。これらの研究が現代のフィボナッチ数の理論の基礎となった。
脚注
注釈
出典
- ↑ Parmanand Singh. "Acharya Hemachandra and the (so called) Fibonacci Numbers". Math. Ed. Siwan, 20(1): pp. 28–30, 1986. ISSN 0047-6269.
- ↑ Parmanand Singh, "The So-called Fibonacci numbers in ancient and medieval India." Historia Mathematica 12(3), pp. 229–244, 1985.
- ↑ 3.0 3.1 3.2 3.3 3.4 奥村晴彦 『C言語による最新アルゴリズム事典』 技術評論社、1991年。ISBN 4-87408-414-1。
- ↑ J. H. E. Cohn, On square Fibonacci numbers, J. London Math. Soc. 39 (1964), pp. 537–540.
- ↑ London, Hymie; Finkelstein, Raphael (1969), “On Fibonacci and Lucas numbers which are perfect powers”, Fibonacci Quart. 7 (5): 476–481, Part1, Part2, Correction
- ↑ Yann Bugeaud, Maurice Mignotte, Samir Siksek, Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers. Ann. of Math. 163(2006), pp. 969–1018. Yann Bugeaud, Publications, 2006.
- ↑ Ming, Luo (1989), “On triangular Fibonacci numbers”, Fibonacci Quart. 27 (2): 98–108
- ↑ Reciprocal Fibonacci Constant -- from Wolfram MathWorld
- ↑ 数学広場の別名「ひまがり広場」の由来:数学と 黄金花『ひまわり』 (PDF) (愛媛県立丹原高等学校)
- ↑ 第14回:全ての植物をフィボナッチの呪いから救い出す(こんどうしげるの生命科学の明日はどっちだ!?)
- ↑ より多くは、例えば [1] などを見よ
- ↑ R. D. Carmichael, On the numerical factors of the arithmetic forms α n ± β n, Ann. of Math. 15 (1913), pp. 30–70, doi:10.2307/1967797.
参考文献
- 佐藤修一 『自然にひそむ数学 自然と数学の不思議な関係』 講談社〈ブルーバックス 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
- 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(英語). Template:Cite webの呼び出しエラー:引数 accessdate は必須です。
- The Fibonacci Association(フィボナッチ協会)(英語)
- Fibonacci Quarterly Home Page(フィボナッチ・クォータリー)(英語)