フィボナッチ数

フィボナッチ数（フィボナッチすう、英: Fibonacci number）は、イタリアの数学者レオナルド・フィボナッチ（ピサのレオナルド）に因んで名付けられた数である。 フィボナッチ数列（フィボナッチすうれつ、（英: Fibonacci sequence） (Fn) は、次の漸化式で定義される： F0 = 0, F1 = 1, Fn+2 = Fn + Fn+1 (n ≥ 0) 第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か月後から毎月1つがいずつの兎を産む。 兎が死ぬことはない。 この条件の下で、産まれたばかりの1つがいの兎は1年の間に何つがいの兎になるか？ つがいの数は次の表のようになる。どの月のつがいの合計も、その前の2つの月での合計の和となり、フィボナッチ数が現れていることが分かる。 フィボナッチ数列の一般項は次の式で表される： F n = 1 5 { ( 1 + 5 2 ) n − ( 1 − 5 2 ) n } = ϕ n − ( 1 − ϕ ) n 5 = ϕ n − ( − ϕ ) − n 5 {\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}={\frac {\phi ^{n}-(1-\phi )^{n}}{\sqrt {5}}}={\frac {\phi ^{n}-(-\phi )^{-n}}{\sqrt {5}}}} この式は1843年にビネ (Jacques Philippe Marie Binet) が発表したことからビネの公式と呼ばれるが、それ以前の1730年（ド・モアブル）・1765年（オイラー）にも発表されており、ビネは最初の発見者ではない。 なお、この式に現れる ϕ = 1 + 5 2 = 1.618033988749894 ⋯ {\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}=1.618033988749894\cdots } は黄金数で、いくつかの数学的特徴がある。黄金数を作る二次方程式 x2 − x − 1 = 0 の解を α, β (α > β) とすると、上記の一般項は F n = α n − β n α − β = α n α − β + β n β − α {\displaystyle F_{n}={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }}={\frac {\alpha ^{n}}{\alpha -\beta }}+{\frac {\beta ^{n}}{\beta -\alpha }}} と表せる。 また、一般項の第2項 − 1 5 ( 1 − 5 2 ) n {\displaystyle -{\frac {1}{\sqrt {5}}}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}} の絶対値は減少列で、n = 0 のとき 1 5 = 0.447 ⋯ < 1 2 {\displaystyle {\frac {1}{\sqrt {5}}}=0.447\cdots <{\frac {1}{2}}} より、第2項を切り捨てた式は Fn の値を 0.447 以下（n > 4 のとき1%以下）の誤差で与える近似式である。 F n ≒ ϕ n 5 {\displaystyle F_{n}\fallingdotseq {\frac {\phi ^{n}}{\sqrt {5}}}} この誤差の絶対値は0.5未満なので、Fn の正確な整数値は以下の式で得られる。 F n = ⌊ ϕ n 5 + 1 2 ⌋ = ⌊ 1 5 ( 1 + 5 2 ) n + 1 2 ⌋ {\displaystyle F_{n}=\left\lfloor {\frac {\phi ^{n}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor =\left\lfloor {\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{2}}\right\rfloor } ただし、 ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } は床関数である。 なお、後述の負数番への拡張を考慮した場合、n < 0 では逆に一般項の第1項の絶対値が0.5未満となるため、n < 0 における Fn の正確な整数値は以下の式で得られる。 F n = − ⌊ ( − ϕ ) − n 5 + 1 2 ⌋ = − ⌊ 1 5 ( 1 − 5 2 ) n + 1 2 ⌋ {\displaystyle F_{n}=-\left\lfloor {\frac {(-\phi )^{-n}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor =-\left\lfloor {\frac {1}{\sqrt {5}}}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{2}}\right\rfloor } これらのことから、任意の整数 n における Fn の正確な整数値は以下の式で得られる。 F n = ( sgn ⁡ n ) ⌊ { ( sgn ⁡ n ) ϕ } | n | 5 + 1 2 ⌋ = ( sgn ⁡ n ) ⌊ 1 5 { 1 + ( sgn ⁡ n ) 5 2 } n + 1 2 ⌋ {\displaystyle F_{n}=(\operatorname {sgn} n)\left\lfloor {\frac {\{(\operatorname {sgn} n)\phi \}^{|n|}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor =(\operatorname {sgn} n)\left\lfloor {\frac {1}{\sqrt {5}}}\left\{{\frac {1+(\operatorname {sgn} n){\sqrt {5}}}{2}}\right\}^{n}+{\frac {1}{2}}\right\rfloor } ただし、sgn x は符号関数である。 また、フィボナッチ数列の漸化式は次のように行列表現できる： ( F n + 2 F n + 1 ) = ( 1 1 1 0 ) ( F n + 1 F n ) {\displaystyle {F_{n+2} \choose F_{n+1}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{F_{n+1} \choose F_{n}}} ∴ ( F n + 1 F n F n F n − 1 ) = ( 1 1 1 0 ) n {\displaystyle \therefore {\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}} 母関数は g ( x ) = ∑ n = 0 ∞ F n x n = x 1 − x − x 2 {\displaystyle g(x)=\textstyle \sum \limits _{n=0}^{\infty }F_{n}x^{n}={\dfrac {x}{1-x-x^{2}}}} である。 フィボナッチ数列の隣接2項の商は黄金数 φ に収束する。この性質は初期値 (F0 = 0, F1 = 1) に依らない。 lim n → ∞ F n F n − 1 = ϕ {\displaystyle \lim _{n\to \infty }{\frac {F_{n}}{F_{n-1}}}=\phi } これは次のように導出される： x = lim n → ∞ F n F n − 1 {\displaystyle x=\lim _{n\to \infty }{\frac {F_{n}}{F_{n-1}}}} が収束するとすれば、 x = lim n → ∞ F n − 1 + F n − 2 F n − 1 = lim n → ∞ ( 1 + 1 F n − 1 / F n − 2 ) = 1 + 1 x {\displaystyle x=\lim _{n\to \infty }{\frac {F_{n-1}+F_{n-2}}{F_{n-1}}}=\lim _{n\to \infty }\left(1+{\frac {1}{F_{n-1}/F_{n-2}}}\right)=1+{\frac {1}{x}}} x 2 − x − 1 = 0 {\displaystyle x^{2}-x-1=0} 自然数 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 また、次の関係式が知られている。 ∑ k = 1 ∞ F k n k = n n 2 − n − 1 {\displaystyle \sum _{k=1}^{\infty }{\frac {F_{k}}{n^{k}}}={\frac {n}{n^{2}-n-1}}} フィボナッチ数のうち平方数であるのは F1 = F2 = 1, F12 = 144 のみ (Cohn 1964)、立方数であるのは F1 = F2 = 1, F6 = 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）。 フィボナッチ数は完全数にはならない。より一般に、フィボナッチ数は倍積完全数にもならず、2つのフィボナッチ数の商も完全数にはならない。 フィボナッチ数列の逆数和は収束し、記号 ψ で表される。 ψ = ∑ n = 1 ∞ 1 F n = 1 1 + 1 1 + 1 2 + 1 3 + ⋯ = 3.35988566 ⋯ {\displaystyle \psi =\sum _{n=1}^{\infty }{\frac {1}{F_{n}}}={\frac {1}{1}}+{\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{3}}+\cdots =3.35988566\cdots } この ψ が無理数であることは証明されているが (André-Jeannin 1989)、超越数であるかどうかは分かっていない。 任意の正の整数は、1つ以上の連続しない相異なるフィボナッチ数の和として一意に表すことができる（ゼッケンドルフの定理）。 再帰的処理の例としてよく紹介される。以下はPythonでの例。 def fibonacci(n): if n == 0 or n == 1: return n else: return fibonacci(n - 2) + fibonacci(n - 1) def fibonacci(n): a, b = 1, 0 for _ in range(n): a, b = b, a + b return b def fibonacci(n): return round((((1 + 5 ** 0.5) / 2) ** n - ((1 - 5 ** 0.5) / 2) ** n) / 5 ** 0.5) しかし、上記例1のプログラムでは n が与えられてから Fn が求まるまでに F n ∝ ϕ n {\displaystyle F_{n}\propto \phi ^{n}} 回の関数呼び出しが発生する（すなわち指数時間の計算となる）ため、実用的ではない。したがって通常は、例4に示すような指数関数的なコールを必要としない実装を行うか、線形時間で計算するためにメモ化などの手法を用いる。さらに、n が大きい場合には一般項の公式（上記例3）や行列表現を利用して対数時間（英語版）での計算を行う。 def fibonacci(n, a = 0, b = 1): if n > 1: return fibonacci(n - 1, b, a + b) return b フィボナッチ数は自然界の現象に数多く出現する。 また、フィボナッチ数列が生み出す螺旋は、世界で最も美しい螺旋だと言われている。 　ヨハネス・ケプラーは1611年に発表した小論文「深淵の贈り物あるいは六角形の雪について」において、フィボナッチ数を自己を増殖する比例と呼び、植物の種子の能力の現れであると論じた。 花びらの数はフィボナッチ数であることが多い。（⇒　この主張の根拠となる出典を明示してください。統計データでは、4枚の花は3枚と同程度に存在します。キク科の舌状花はある範囲で分布し、このように枚数は固定されません。） フィボナッチ数は、花びらの枚数も決めているらしい。（『聖なる幾何学』p63より） 3枚：ユリ、アヤメ、エンレイソウ 5枚：オダマキ、サクラソウ、キンボウゲ、ノイバラ、ヒエンソウ 8枚：デルフィニウム属、サンギナリア、コスモス 13枚：シネラリア、コーンマリゴールド 21枚：チコリー、オオハンゴンソウ 34枚：オオバコ、シロバナムシヨケギク 55枚：ユウゼンギク 89枚：ミケルマス・デイジー 花弁の数が144に達することはない。この数は、他の自然界に見られるフィボナッチ数の例でも限界になっていることが多い。 アブラナやダイコンの花びらは4枚であり、植物学では花式図より3数性、4数性、5数性で分類される。 植物の花や実に現れる螺旋の数もフィボナッチ数であることが多い。 ヒマワリの螺旋の数はフィボナッチ数とされることもあるが、螺旋の数が多い場合、中心から離れると螺旋の隙間にも種ができてしまうため、途中から枝分かれしてフィボナッチ数にならないこともある。 パイナップルの螺旋の数は時計回りは13、反時計回りは8になっている。 葉序（植物の葉の付き方）はフィボナッチ数と関連している。（⇒　出典ならびに根拠を明示してください。） らせん葉序におけるシンパー・ブラウンの法則はフィボナッチ数列と関連するが、「近似値を示すにすぎず、またこれにあてはまらない例もある」（岩波生物学辞典）。 ハチやアリなど、オスに父親がない家系を辿っていくとフィボナッチ数列が現れる（父母2匹、祖父母3匹、曽祖父母5匹、高祖父母8匹…）。 n 段の階段を1段または2段ずつ登るときに、登る場合の数は Fn+1 通りある。 ●と○を合わせて n 個並べる。●が2個以上続かないように一列に並べる方法は Fn+2 通りある。 為替などのテクニカル分析で、フィボナッチ・リトレースメントという手法がよく使われている。 フィボナッチ数列は、漸化式 Fn = Fn−1 + Fn−2 を全ての整数 n に対して適用することにより、n が負の整数の場合に拡張できる。そして F−n = (−1)n+1Fn が成り立つ。この式より、負の番号の項は次のようになる。 フィボナッチ数列の定義である初期値や漸化式をやや変更して、類似の数列が作れる。 フィボナッチ数列は各項が先行する二項の和であるものであったが、それを「先行する k 項の和」と置き換えた一般化 F n + k ( k ) := F n + k − 1 ( k ) + F n + k − 2 ( k ) + ⋯ + F n ( k ) ( n ≥ 0 ) {\displaystyle F_{n+k}^{(k)}:=F_{n+k-1}^{(k)}+F_{n+k-2}^{(k)}+\dotsb +F_{n}^{(k)}\quad (n\geq 0)} を考えることができる。ただし、初期値は 1 で埋める（1-fil型） F 0 ( k ) = F 1 ( k ) = ⋯ = F k − 1 ( k ) = 1 {\displaystyle F_{0}^{(k)}=F_{1}^{(k)}=\dotsb =F_{k-1}^{(k)}=1} あるいは 0 で埋める（0-fil型） F 0 ( k ) = F 1 ( k ) = ⋯ = F k − 2 ( k ) = 0 , F k − 1 ( k ) = 1 {\displaystyle F_{0}^{(k)}=F_{1}^{(k)}=\dotsb =F_{k-2}^{(k)}=0,\quad F_{k-1}^{(k)}=1} などを取るのが一般的である。これらフィボナッチ数列の類似物を、項数 k に対応するラテン語またはギリシャ語に由来する倍数接頭辞を「フィボナッチ」と組み合わせた名称で呼ぶ。 特に直前の三項の和として各項が定まるトリボナッチ数列は、フィボナッチ数列に次いでよく調べられている。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) トリボナッチ数列の一般項は次で表される。 T n = α n ( α − β ) ( α − γ ) + β n ( β − γ ) ( β − α ) + γ n ( γ − α ) ( γ − β ) {\displaystyle T_{n}={\frac {\alpha ^{n}}{(\alpha -\beta )(\alpha -\gamma )}}+{\frac {\beta ^{n}}{(\beta -\gamma )(\beta -\alpha )}}+{\frac {\gamma ^{n}}{(\gamma -\alpha )(\gamma -\beta )}}} ただし、α, β, γ は三次方程式 x3 − x2 − x − 1 = 0 の3解 α = 1 3 ( 1 + 19 − 3 33 3 + 19 + 3 33 3 ) β = 1 3 ( 1 + ω 19 − 3 33 3 + ω ¯ 19 + 3 33 3 ) γ = 1 3 ( 1 + ω ¯ 19 − 3 33 3 + ω 19 + 3 33 3 ) {\displaystyle {\begin{aligned}\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{aligned}}} であり、ここで ω = − 1 + 3 i 2 {\displaystyle \omega ={\frac {-1+{\sqrt {3}}i}{2}}} （1 の虚立方根） である。 また、上記の α をトリボナッチ定数という。これはフィボナッチ数列における黄金数に当たる定数で、トリボナッチ数列の隣接2項間の商はトリボナッチ定数に収束する： lim n → ∞ T n T n − 1 = α = 1.839286755214161 ⋯ {\displaystyle \lim _{n\to \infty }{\frac {T_{n}}{T_{n-1}}}=\alpha =1.839286755214161\cdots } 直前の四項の和に変更したテトラナッチ数列も同様に様々なことが知られている。同様にオフセット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解を α, β, γ, δ として、 T n = α n ( α − β ) ( α − γ ) ( α − δ ) + β n ( β − γ ) ( β − δ ) ( β − α ) + γ n ( γ − δ ) ( γ − α ) ( γ − β ) + δ n ( δ − α ) ( δ − β ) ( δ − γ ) {\displaystyle 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 )}}} となる。 フィボナッチ数列の最初の2項を 2, 1 に置き換えた数列の項をリュカ数という。 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, … (OECS A000032) この数列の一般項は L n = ( 1 + 5 2 ) n + ( 1 − 5 2 ) n = ϕ n + ( 1 − ϕ ) n = ϕ n + ( − ϕ ) − n {\displaystyle 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}}} と表される。 フィボナッチ数列やリュカ数の列を一般化したものがリュカ数列であり、1878年にエドゥアール・リュカが体系的な研究を行い、1913年にロバート・ダニエル・カーマイケル（英語版）がその結果を整理、拡張した。これらの研究が現代のフィボナッチ数の理論の基礎となった。