フィボナッチ数
フィボナッチ数(フィボナッチすう、Fibonacci number)は、イタリアの数学者レオナルド・フィボナッチ(ピサのレオナルド)に因んで名付けられた数である。
フィボナッチ数列 (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か月後から毎月1つがいずつの兎を産む。
兎が死ぬことはない。
この条件の下で、産まれたばかりの1つがいの兎は1年の間に何つがいの兎になるか?
つがいの数は次の表のようになる。どの月のつがいの合計も、その前の2つの月での合計の和となり、フィボナッチ数が現れていることが分かる。
フィボナッチ数列の一般項は次の式で表される:
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年にビネ (en) が発表したことからビネの公式と呼ばれるが、それ以前の1730年(ド・モアブル)・1765年(オイラー)にも発表されており、ビネは最初の発見者ではない。
なお、この式に現れる
\phi = \frac{1+\sqrt{5}{2} = 1.618 033 988 749 894\cdots
は黄金数で、いくつかの数学的特徴がある。黄金数を作る二次方程式 x2 − x − 1  0 の解を α, β (α > β) とすると、上記の一般項は
F_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}=\frac{\alpha^n}{\alpha-\beta}+\frac{\beta^n}{\beta-\alpha}
と表せる。
また、一般項の第2項 -\frac{1}{\sqrt{5} \left( \frac{1-\sqrt{5}{2} \right)^n の絶対値は減少列で、n = 0 のとき \frac{1}{\sqrt{5} = 0.447\cdots < \frac{1}{2} より、第2項を切り捨てた式は Fn の値を 0.447 以下(n > 4 のとき1%以下)の誤差で与える近似式である。
F_n \fallingdotseq \frac{\phi^n}{\sqrt{5}
この誤差の絶対値は0.5未満なので、Fn の正確な整数値は以下の式で得られる。
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
ただし、\lfloor x\rfloor は床関数である。
なお、後述の負数番への拡張を考慮した場合、n < 0 では逆に一般項の第1項の絶対値が0.5未満となるため、n < 0 における Fn の正確な整数値は以下の式で得られる。
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) \left\lfloor \frac{\{(\sgn n)\phi\}^〔n|}{\sqrt{5} + \frac{1}{2} \right\rfloor
= (\sgn n) \left\lfloor \frac{1}{\sqrt{5}\left\{ \frac{1+(\sgn n)\sqrt{5}{2} \right\}^n + \frac{1}{2} \right\rfloor
ただし、sgn x は符号関数である。
また、フィボナッチ数列の漸化式は次のように行列表現できる:
{F_{n+2} \choose F_{n+1} = \begin{pmatrix}
1 &1 \\
1 &0
\end{pmatrix} {F_{n+1} \choose F_n}
\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) = \textstyle\sum\limits_{n=0}^{\infty} F_n x^n = \dfrac{x}{1-x-x^2}
である。
フィボナッチ数列の隣接2項の商は黄金数 φ に収束する。この性質は初期値 (F0 = 0, F1 = 1) に依らない。
\lim_{n \to \infty} \frac{F_n}{F_{n-1} = \phi
これは次のように導出される:
x = \lim_{n \to \infty} \frac{F_n}{F_{n-1} が収束するとすれば、
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
自然数 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 を割り切る。ここで ( / ) はルジャンドル記号である。
フィボナッチ数の累和や累積について以下の式が成り立つ。
また、次の関係式が知られている。
\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つのフィボナッチ数の商も完全数にはならない。
フィボナッチ数列の逆数和は収束し、記号 ψ で表される。
\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での例。
しかし、上記例1のプログラムでは n が与えられてから Fn が求まるまでに F_n \propto \phi^n 回の関数呼び出しが発生する(すなわち指数時間の計算となる)ため、実用的ではない。したがって通常は、線形時間で計算するためにメモ化などの手法を用いる。さらに、n が大きい場合には一般項の公式(上記例3)や行列表現を利用して対数時間での計算を行う。
フィボナッチ数は自然界の現象に数多く出現する。
また、フィボナッチ数列が生み出す螺旋は、世界で最も美しい螺旋だと言われている。
ヨハネス・ケプラーは1611年に発表した小論文「深淵の贈り物あるいは六角形の雪について」において、フィボナッチ数を自己を増殖する比例と呼び、植物の種子の能力の現れであると論じた。
花びらの数はフィボナッチ数であることが多い。
3枚:ユリ、アヤメ、エンレイソウ
5枚:オダマキ、サクラソウ、キンボウゲ、ノイバラ、ヒエンソウ
8枚:デルフィニウム属、サンギナリア、コスモス
13枚:シネラリア、コーンマリゴールド
21枚:チコリー、オオハンゴンソウ
34枚:オオバコ、シロバナムシヨケギク
55枚:ユウゼンギク
89枚:ミケルマス・デイジー
花弁の数が144に達することはない。この数は、他の自然界に見られるフィボナッチ数の例でも限界になっていることが多い。
植物の花や実に現れる螺旋の数もフィボナッチ数であることが多い。
ヒマワリの螺旋の数はフィボナッチ数とされることもあるが、螺旋の数が多い場合、中心から離れると螺旋の隙間にも種ができてしまうため、途中から枝分かれしてフィボナッチ数にならないこともある。
パイナップルの螺旋の数は時計回りは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)} + \dotsb + F_n^{(k)}\quad (n\ge 0)
を考えることができる。ただし、初期値は 1 で埋める(1-fil型)
F_0^{(k)} = F_1^{(k)}=\dotsb=F_{k-1}^{(k)}=1
あるいは 0 で埋める(0-fil型)
F_0^{(k)} = F_1^{(k)}=\dotsb=F_{k-2}^{(k)}=0,\quad F_{k-1}^{(k)}=1
などを取るのが一般的である。これらフィボナッチ数列の類似物を、項数 k に対応するラテン語またはギリシャ語に由来する倍数接頭辞を「フィボナッチ」と組み合わせた名称で呼ぶ当然のことだが "Fibonacci" は人名であって、"fibo-" + "-nacci" や "fi-" + "-bonacci" という構成の合成語でもないし、もちろん "fi-" や "fibo-" が "2" の意味を持つわけでもない(ただし、摩擦音 f と破裂音 b が音韻的に近い関係にあることから 2 を表す "bi-" を "fi-" に結び付けての類推ではあるかもしれない)が、「フィボナッチ」の語を頭から適当な音節分だけ倍数を表す接頭辞で置き換えるという、冗談のような名付けになっている。。
特に直前の三項の和として各項が定まるトリボナッチ数列は、フィボナッチ数列に次いでよく調べられている。0-fil型でオフセットが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 = \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解
\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}
であり、ここで
\omega = \frac{-1 + \sqrt{3} i}{2}(1 の虚立方根)
である。
また、上記の α をトリボナッチ定数という。これはフィボナッチ数列における黄金数に当たる定数で、トリボナッチ数列の隣接2項間の商はトリボナッチ定数に収束する:
\lim_{n \to \infty} \frac{T_n}{T_{n-1} = \alpha = 1.839286755214161\cdots
直前の四項の和に変更したテトラナッチ数列も同様に様々なことが知られている。同様にオフセット0番の 0-fil型は
と書けて、第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 = \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 = \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年にロバート・ダニエル・カーマイケルがその結果を整理、拡張した。これらの研究が現代のフィボナッチ数の理論の基礎となった。