「フィボナッチ数」の版間の差分
→一般項: 母関数 |
|||
142行目: | 142行目: | ||
フィボナッチ数が[[ハーシャッド数]]であるものは [[1]], [[2]], [[3]], [[5]], [[8]], [[21]], [[144]], [[2584]], … ({{OEIS|A117774}})。 |
フィボナッチ数が[[ハーシャッド数]]であるものは [[1]], [[2]], [[3]], [[5]], [[8]], [[21]], [[144]], [[2584]], … ({{OEIS|A117774}})。 |
||
フィボナッチ数は[[完全数]]にはならない<ref name="Luca2000">{{cite journal | first=Florian | last=Luca | title=Perfect Fibonacci and Lucas numbers | journal=Rendiconti del Circolo Matematico di Palermo | year=2000 | volume=49 | issue=2 | pages=313--318 | doi=10.1007/BF02904236 | |
フィボナッチ数は[[完全数]]にはならない<ref name="Luca2000">{{cite journal | first=Florian | last=Luca | title=Perfect Fibonacci and Lucas numbers | journal=Rendiconti del Circolo Matematico di Palermo | year=2000 | volume=49 | issue=2 | pages=313--318 | doi=10.1007/BF02904236 | mr=1765401 | issn=1973-4409 }}</ref>。より一般に、フィボナッチ数は[[倍積完全数]]にもならず<ref name="BGLLHT2011">{{cite journal | first1=Kevin A. | last1=Broughan | first2=Marcos J. | last2=González | first3=Ryan H. | last3=Lewis | first4=Florian | last4=Luca | first5=V. Janitzio | last5=Mejía Huguet | first6=Alain | last6=Togbé | title=There are no multiply-perfect Fibonacci numbers | journal=Integers | year=2011 | volume=11a | pages=A7 | url=http://math.colgate.edu/~integers/vol11a.html | mr=2988067 }}</ref>、2つのフィボナッチ数の比も完全数にはならない<ref name="LucaMH2010">{{cite journal | first1=Florian | last1=Luca | first2= V. Janitzio | last2=Mejía Huguet | title=On Perfect numbers which are ratios of two Fibonacci numbers | journal=Annales Mathematicae at Informaticae | year=2010 | volume=37 | pages=107--124 | url=http://ami.ektf.hu/index.php?vol=37 | mr=2753031 | issn=1787-6117 }}</ref>。 |
||
[[フィボナッチ数列の逆数和|フィボナッチ数の逆数の総和]]はある一定の値に収束し、記号 {{mvar|ψ}} で表される。 |
[[フィボナッチ数列の逆数和|フィボナッチ数の逆数の総和]]はある一定の値に収束し、記号 {{mvar|ψ}} で表される。 |
2020年1月25日 (土) 02:12時点における版
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/db/34%2A21-FibonacciBlocks.png/300px-34%2A21-FibonacciBlocks.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Image_from_Gutza_Wikipedia.jpg/220px-Image_from_Gutza_Wikipedia.jpg)
フィボナッチ数(フィボナッチすう、英: Fibonacci number)は、イタリアの数学者レオナルド・フィボナッチ(ピサのレオナルド)にちなんで名付けられた数である。
概要
n 番目のフィボナッチ数を Fn で表すと、Fn は再帰的に
- F0 = 0,
- F1 = 1,
- Fn + 2 = Fn + Fn + 1 (n ≧ 0)
で定義される。これは、2つの初期条件を持つ漸化式である。
この数列 (Fn)は
- 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]:
この式は1843年にビネ (Jacques Philippe Marie Binet) が発表したことからビネの公式と呼ばれるが、それ以前の1730年 (ド・モアブル)・1765年(オイラー)にも発表されており、ビネは最初の発見者ではない。
なお、この式に現れる、
という値は、黄金比という値で、いくつかの数学的特徴がある。この黄金比をつくる数式 x2 − x − 1 = 0 の解をα , β (α > β)としたとき,上記の一般項は
と表せる。
また φ を表す第2項の絶対値は n = 0 のときの が最大で、それを超えることはない。従って、第2項を略した次の式は Fn の値を 0.447 以下(n > 4 のとき1%以下)の誤差で与える近似式である。
この誤差の絶対値は0.5未満なので、Fn の正確な整数値は以下の式で得られる[3]。
ただし、 は床関数である。
なお、後述の負数番への拡張を考慮した場合、n < 0 では逆に一般項の第1項の絶対値が0.5未満となるため、n < 0 における Fn の正確な整数値は以下の式で得られる。
これらのことから、任意の整数 n における Fn の正確な整数値は以下の式で得られる。
ただし、sgn x は符号関数である。
また、フィボナッチ数列の漸化式は次のように行列表現できる[3]:
ゆえに
母関数は
である。
性質
隣り合うフィボナッチ数の比は黄金比 φ に収束する。この性質は初期値 (F0 = 0, F1 = 1) に依らない。
これは次のように導出される:
が収束するとすれば、
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
また、次の関係式が知られている。
フィボナッチ数のうち平方数であるものは 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]。
フィボナッチ数の逆数の総和はある一定の値に収束し、記号 ψ で表される。
この ψ が無理数であることは証明されているが (André-Jeannin 1989)、超越数であるかどうかは分かっていない。
任意の正の整数は、1つ以上の連続しない相異なるフィボナッチ数の和として一意に表すことができる(ゼッケンドルフの定理)。
プログラミング言語での実装
例1(再帰的処理による実装例)
int fibonacci(int n) {
switch (n) {
case 0:
case 1:
return n;
default:
return fibonacci(n - 2) + fibonacci(n - 1);
}
}
例2(ループ処理による実装例)
int fibonacci(int n) {
int i, a, b, c;
for (i = 0, b = 1, c = 0; i < n; i++) {
a = b;
b = c;
c = a + b;
}
return c;
}
例3(一般項による実装例)
#include <math.h>
int fibonacci(int n) {
return round((pow((1 + sqrt(5)) / 2, n)
- pow((1 - sqrt(5)) / 2, n)) / sqrt(5));
}
しかし、上記例1のプログラムでは n が与えられてから Fn が求まるまでに 回の関数呼び出しが発生する(すなわち指数時間の計算となる)ため、実用的ではない。したがって通常は、線形時間で計算するためにメモ化などの手法を用いる。さらに、n が大きい場合には一般項の公式(上記例3、ただし#include <math.h>
を記載しておく必要あり)や行列表現[3]を利用して対数時間での計算を行う。
その他の話題
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/44/Helianthus_whorl.jpg/250px-Helianthus_whorl.jpg)
- フィボナッチ数は自然界の現象に数多く出現する。
- 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 項の和」と置き換えた一般化を考えることができる。ただし、初期値は 1 で埋める (1-fil型) あるいは 0 で埋める (0-fil型) などを取るのが一般的である。これらフィボナッチ数列の類似物を、項数 k に対応するラテン語またはギリシャ語に由来する倍数接頭辞を「フィボナッチ」と組み合わせた名称で呼ぶ[注釈 1]。
k | 接頭辞[15] | 名称 | 整数列大辞典 |
---|---|---|---|
3 | tri- | トリボナッチ数 | 0 fil: A000073 1 fil: A000213 |
4 | tetra- | テトラナッチ数 | 0 fil: A000078 1 fil: A000288 |
5 | penta- | ペンタナッチ数 | 0 fil: A001591 1 fil: A000322 |
6 | hexa- | ヘキサナッチ数 | 0 fil: A001592 1 fil: A000383 |
7 | hepta- | ヘプタナッチ数 | 0 fil: A122189 1 fil: A060455 |
8 | octa- | オクタナッチ数 | 0 fil: A079262 1 fil: A123526 |
9 | nona- | ノナ(ボ)ナッチ数 | 0 fil: A163551 1 fil: A127193 |
10 | deca- | デカ(ボ)ナッチ数 | 1 fil: A127194 |
11 | undeca- | ウンデカ(ボ)ナッチ数 | 1 fil: A127624 |
12 | dodeca- | ドデカ(ボ)ナッチ数 | 1 fil: A207539 |
⋮ | |||
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 A73).
トリボナッチ数列の一般項は次で表される。
ただし、α, β, γ は三次多項式 x3 − x2 − x − 1 の三根
であり、ここに
は 1 の虚立方根である。
また、上の3つの根のうち、実数解 α のことをトリボナッチ定数という。これはフィボナッチ数列の黄金比にあたる定数で、トリボナッチ数列の隣り合う2項間の比は、トリボナッチ定数に収束する:
テトラナッチ数
直前の四項の和に変更したテトラナッチ数列も同様に様々なことが知られている。同様にオフセット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 A78).
一般項は、四次多項式 の四つの根を α, β, γ, δ として、
のようになる。
初期値の変更
リュカ数
フィボナッチ数列の最初の2項を 2, 1 に置き換えた数列の項をリュカ数という。
- 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, … A000032
この数列の一般項は
と表される。
フィボナッチ数列やリュカ数の列を一般化したものがリュカ数列であり、1878年にエドゥアール・リュカが体系的な研究を行い、1913年にロバート・ダニエル・カーマイケルがその結果を整理、拡張した[16]。これらの研究が現代のフィボナッチ数の理論の基礎となった。
脚注
注釈
出典
- ^ 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.
- ^ a b c d e 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、305頁。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
- ^ Luca, Florian (2000). “Perfect Fibonacci and Lucas numbers”. Rendiconti del Circolo Matematico di Palermo 49 (2): 313--318. doi:10.1007/BF02904236. ISSN 1973-4409. MR1765401.
- ^ Broughan, Kevin A.; González, Marcos J.; Lewis, Ryan H.; Luca, Florian; Mejía Huguet, V. Janitzio; Togbé, Alain (2011). “There are no multiply-perfect Fibonacci numbers”. Integers 11a: A7. MR2988067 .
- ^ Luca, Florian; Mejía Huguet, V. Janitzio (2010). “On Perfect numbers which are ratios of two Fibonacci numbers”. Annales Mathematicae at Informaticae 37: 107--124. ISSN 1787-6117. MR2753031 .
- ^ Reciprocal Fibonacci Constant -- from Wolfram MathWorld
- ^ 数学広場の別名「ひまがり広場」の由来:数学と 黄金花『ひまわり』 (PDF) (愛媛県立丹原高等学校)
- ^ 聖なる幾何学 スティーヴン・スキナー著 P63「植物成長の幾何学」より抜粋
- ^ 第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年1月20日。ISBN 4-06-257201-X。
- 中村滋『フィボナッチ数の小宇宙(ミクロコスモス) フィボナッチ数、リュカ数、黄金分割』日本評論社、2002年9月。ISBN 4-535-78281-4。
- 中村滋『フィボナッチ数の小宇宙(ミクロコスモス) フィボナッチ数、リュカ数、黄金分割』(改訂版)日本評論社、2008年1月。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年6月。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, Volume 1 (2nd ed.), Wiley, ISBN 978-1-118-74212-9
- Koshy, Thomas (2019-01-07), Fibonacci and Lucas Numbers with Applications, Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts, Volume 2 (2nd ed.), Wiley, ISBN 978-1-118-74208-2
- 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 - 『算盤の書』の英訳。
- 中村 滋:「日本フィボナッチ協会の20年」、日本評論社、雑誌:数学セミナー(2018年8月)、57巻、8号、pp.48-53。
関連項目
外部リンク
- 竹之内脩『フィボナッチ数列』 - コトバンク
- 『{{{2}}}』 - 高校数学の美しい物語
- Weisstein, Eric W. "Fibonacci Number". mathworld.wolfram.com (英語).
- The Fibonacci Association(フィボナッチ協会)(英語)
- Fibonacci Quarterly Home Page(フィボナッチ・クォータリー)(英語)
- 日本フィボナッチ協会 第14回研究集会報告書2016年8月日本フィボナッチ協会
- 日本フィボナッチ協会 第16回研究集会報告書2018年8月日本フィボナッチ協会