フィボナッチ数

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

## 概要
  は、次の漸化式で定義される：
:\begin{cases}
F_0 = 0 & \, \\
F_1 = 1 & \, \\
F_n = F_{n-1}+F_{n-2} &(n\geqq 2)
\end{cases}


第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, …（）
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{\varphi^n - (1-\varphi)^n}{\sqrt{5}}
= \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}
この式は1843年にビネ（）が発表したことからビネの公式と呼ばれるが、それ以前の1730年（ド・モアブル）・1765年（オイラー）にも発表されており、ビネは最初の発見者ではない。

なお、この式に現れる
:\varphi = \frac{1+\sqrt{5}}{2} = 1.618 033 988 749 894\cdots
は**[[黄金比|黄金数]]**で、いくつかの数学的特徴がある。黄金数を作る二次方程式  の解を  とすると、上記の一般項は
:F_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}=\frac{\alpha^n}{\alpha-\beta}+\frac{\beta^n}{\beta-\alpha}
と表せる。

また、一般項の第2項  の絶対値は減少列で、 のとき  より、第2項を切り捨てた式は  の値を 0.447 以下（ のとき1%以下）の誤差で与える近似式である。
:F_n \fallingdotseq \frac{\varphi^n}{\sqrt{5}}
この誤差の絶対値は0.5未満なので、 の正確な整数値は以下の式で得られる。
:F_n
= \left\lfloor \frac{\varphi^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
ただし、 は床関数である。

なお、後述の負数番への拡張を考慮した場合、 では逆に一般項の第1項の絶対値が0.5未満となるため、 における  の正確な整数値は以下の式で得られる。
:F_n
= - \left\lfloor \frac{(-\varphi)^{-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
これらのことから、任意の整数  における  の正確な整数値は以下の式で得られる。
:F_n
= (\sgn n) \left\lfloor \frac{\{(\sgn n)\varphi\}^}{\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
ただし、 は符号関数である。

### 行列表現
また、フィボナッチ数列の漸化式は次のように行列表現できる：
:\begin{bmatrix} F_{n+1} \\F_{n} \end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix} \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix},\;\;\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}
これらを並べて表記すると、
:\begin{align}
\begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix} &= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}\begin{bmatrix}
F_{n} & F_{n-1} \\
F_{n-1} & F_{n-2}
\end{bmatrix} \\
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^2\begin{bmatrix}
F_{n-1} & F_{n-2} \\
F_{n-2} & F_{n-3}
\end{bmatrix} \\
&= \cdots \\
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n\begin{bmatrix}
F_{1} & F_{0} \\
F_{0} & F_{-1}
\end{bmatrix} \\
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n\begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix}
\end{align}
:\therefore
\begin{align}
\begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\end{align}
ここで、 は、漸化式  に  を代入すると得られる（詳細は後述の負数番への拡張を参照）。

更に、 を  で置換すると、
:\begin{align}
\begin{bmatrix}
F_{2n+1} & F_{2n} \\
F_{2n} & F_{2n-1}
\end{bmatrix} &= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{2n} = \left ( \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n \right )^2 = \begin{bmatrix}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{bmatrix}^2 \\
&= \begin{bmatrix}
{F_n}^2 + {F_{n+1}}^2 & (F_{n-1} + F_{n+1}) F_n \\
(F_{n-1} + F_{n+1}) F_n & {F_{n-1}}^2 + {F_n}^2
\end{bmatrix}
\end{align}

よって、
:\begin{align}
F_{2n+1} &= {F_n}^2 + {F_{n+1}}^2 \\
F_{2n} &= (F_{n-1} + F_{n+1}) F_n = (2 F_{n-1} + F_n) F_n = (2 F_{n+1} - F_n) F_n \\
F_{2n-1} &= {F_{n-1}}^2 + {F_n}^2
\end{align}

母関数は
:g(x) = \sum\limits_{n=0}^{\infty} F_n x^n = \dfrac{x}{1-x-x^2}
である。

また、この行列表現を基に、以下のような漸化式を考えることができる。

:\begin{cases}
F_0 = 0 & \, \\
F_1 = 1 & \, \\
F_n = {F_q}^2+\{ 1+(-1)^n \}F_{q-1}F_q+\dfrac{1-(-1)^n}{2}{F_{q+1}}^2 &\left( n\geqq 2,\;q=\left\lfloor \dfrac{n}{2} \right\rfloor \right)
\end{cases}


## 性質
フィボナッチ数列の隣接2項の商は黄金数  に収束する。この性質は初期値 () に依らない。
:\lim_{n \to \infty} \frac{F_n}{F_{n-1}} = \varphi
これは次のように導出される：
: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
* 自然数  の最大公約数を  とすると、 と  の最大公約数は  である。
これより以下を導くことができる。
:*  が  で割り切れるならば、 は  で割り切れる。
:* 連続する2数は互いに素であることより、隣り合うフィボナッチ数も互いに素である。
:*  が偶数となるのは  が 3 の倍数となるときと一致する。
:*  が 5 の倍数となるのは  が 5 の倍数となるときと一致する。
:*  が 2 でも 5 でもない素数のとき、 とおくと  は  を割り切る。ここで  はルジャンドル記号である。

フィボナッチ数の累和や累積について以下の式が成り立つ。
*
*
*
*
*
また、次の関係式が知られている。
:\sum_{k=1}^\infty \frac{F_k}{n^{k}} = \frac{n}{n^2-n-1}
フィボナッチ数のうち平方数であるのは ,  のみ（Cohn 1964）、立方数であるのは ,  のみ（London and Finkelstein 1969）である。フィボナッチ数のうち累乗数であるのはこれしかない（Bugeaud, Mignotte, Siksek 2006）。このブジョー・ミニョット・シクセクの定理はフェルマー予想と同様の方針で証明された。（）
 
フィボナッチ数で素数であるのは 2, 3, 5, 13, 89, 233, 1597, 28657, … である（）。また、これらはフィボナッチ素数と呼ばれる。

フィボナッチ数で三角数であるのは 1, 3, 21, 55（）のみであることは Vern Hoggatt によって予想されていたが、のちに Luo Ming によって証明された。

フィボナッチ数でハーシャッド数であるのは 1, 2, 3, 5, 8, 21, 144, 2584, …（）。

フィボナッチ数は完全数にはならない。より一般に、フィボナッチ数は倍積完全数にもならず、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つ以上の連続しない相異なるフィボナッチ数の和として一意に表すことができる（ゼッケンドルフの定理）。

パスカルの三角形で数字を桂馬跳びのように拾うと、総和がフィボナッチ数になる数列が現れる。
また  が十分に大きいとき、フィボナッチ数列の漸化式を遡らせるとパスカルの三角形が現れ、桂馬跳びに同じ項が現れる。

F_n = F_{n-1}+F_{n-2} = F_{n-2}+2F_{n-3}+F_{n-4} = F_{n-3}+3F_{n-4}+3F_{n-5}+F_{n-6}

## プログラミング言語での実装
再帰的処理の例としてよく紹介される。以下はPythonでの例。

ただし、下記実装例の内、#負数番への拡張に対応しているのは例5・例6のみである。

### 例1（再帰的処理による実装例）
このプログラムでは、 が与えられてから  が求まるまでに  回の関数呼び出しが発生する（すなわち指数時間の計算となる）ため、実用的ではない。したがって通常は、線形時間で計算するためにメモ化などの手法を用いる他、後述するように様々な実装例が検討されている。

メモ化の例を挙げると、

### 例2（ループ処理による実装例）

### 例3（指数関数的なコールを必要としない再帰的処理による実装例）
 が1以上の場合に第2・第3の引数を上記例2と同じ要領で順次更新していくことで、コール回数を  回に抑えられる為、線形時間で処理できる。

### 例4（対数時間での再帰的処理による実装例）
#行列表現で導出した漸化式（以下に再掲）を用いることで、再帰的処理でも対数時間で処理できる。
:\begin{cases}
F_0 = 0 & \, \\
F_1 = 1 & \, \\
F_n = {F_q}^2+\{ 1+(-1)^n \}F_{q-1}F_q+\dfrac{1-(-1)^n}{2}{F_{q+1}}^2 &\left( n\geqq 2,\;q=\left\lfloor \dfrac{n}{2} \right\rfloor \right)
\end{cases}
ただし、プログラム上は0を掛けるからと言ってその対象の値が計算されない訳では無い為（短絡評価されない）、条件式による分岐で表記している。

### 例5（一般項による実装例）
浮動小数点型を使用すると計算誤差が発生する為、モジュールを用いている。

なお、先述の通りフィボナッチ数列の一般項は、引数  の符号によって2項の内いずれかが0.5未満となることから、符号関数及び床関数を用いて以下のように表すことができた。
:F_n = (\sgn n)\left\lfloor \frac{\{ (\sgn n)\varphi \}^}{\sqrt{5}}+\frac{1}{2} \right\rfloor（#一般項より再掲）
このことから、以下のように実装することで冪乗演算の回数を減らすことが出来る。

### 例6（行列表現での実装例）
:\begin{bmatrix}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n（#行列表現より再掲）
より、 を  に置換すると、
:\begin{bmatrix}
F_n & F_{n-1} \\
F_{n-1} & F_{n-2}
\end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{n-1}
従って、 は、上式右辺（の具体的な計算値）の左上成分に等しい。

行列の冪を簡潔に記述する為にSymPyを用いた。

## その他の話題

250px|thumb|ヒマワリの種は螺旋状に並んでおり、螺旋の数を数えていくとフィボナッチ数が現れる
* フィボナッチ数は自然界の現象に数多く出現する。
*また、フィボナッチ数列が生み出す螺旋は、世界で最も美しい螺旋だと言われている。
ヨハネス・ケプラーは1611年に発表した小論文「新年の贈り物あるいは六角形の雪について」において、フィボナッチ数を自己を増殖する比例と呼び、植物の種子の能力の現れであると論じた。
*花びらの数はフィボナッチ数であることが多い。
*フィボナッチ数は、花びらの枚数も決めているらしい。（『聖なる幾何学』p63より）
** 3枚：ユリ、アヤメ、エンレイソウ
** 5枚：オダマキ、サクラソウ、キンボウゲ、ノイバラ、ヒエンソウ
** 8枚：デルフィニウム属、サンギナリア、コスモス
** 13枚：シネラリア、コーンマリゴールド
** 21枚：チコリー、オオハンゴンソウ
** 34枚：オオバコ、シロバナムシヨケギク
** 55枚：ユウゼンギク
** 89枚：ミケルマス・デイジー
*** 花弁の数が144に達することはない。この数は、他の自然界に見られるフィボナッチ数の例でも限界になっていることが多い。

* アブラナやダイコンの花びらは4枚であり、植物学では花式図より3数性、4数性、5数性で分類される。
*植物の花や実に現れる螺旋の数もフィボナッチ数であることが多い。
**ヒマワリの螺旋の数はフィボナッチ数とされることもあるが、螺旋の数が多い場合、中心から離れると螺旋の隙間にも種ができてしまうため、途中から枝分かれしてフィボナッチ数にならないこともある。
*パイナップルの螺旋の数は時計回りは13、反時計回りは8になっている。
*葉序（植物の葉の付き方）はフィボナッチ数と関連している。(シンパー=ブラウンの法則)
*らせん葉序におけるシンパー・ブラウンの法則はフィボナッチ数列と関連するが、「近似値を示すにすぎず、またこれにあてはまらない例もある」（岩波生物学辞典）。
*ハチやアリなど、オスに父親がない家系を辿っていくとフィボナッチ数列が現れる（父母2匹、祖父母3匹、曽祖父母5匹、高祖父母8匹…）。
* 段の階段を1段または2段ずつ登るときに、登る場合の数は  通りある。
* ●と○を合わせて  個並べる。●が2個以上続かないように一列に並べる方法は  通りある。
*為替などのテクニカル分析で、フィボナッチ・リトレースメントという手法がよく使われている。

## 負数番への拡張
フィボナッチ数列は、漸化式  を全ての整数  に対して適用することにより、 が負の整数の場合に拡張できる。そして  が成り立つ。この式より、負の番号の項は次のようになる。

## 類似の数列
フィボナッチ数列の定義である初期値や漸化式をやや変更して、類似の数列が作れる。

### 項数の変更
フィボナッチ数列は各項が先行する二項の和であるものであったが、それを「先行する  項の和」と置き換えた一般化
: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
などを取るのが一般的である。これらフィボナッチ数列の類似物を、項数  に対応するラテン語またはギリシャ語に由来する倍数接頭辞を「フィボナッチ」と組み合わせた名称で呼ぶ。

#### トリボナッチ数
特に直前の三項の和として各項が定まるトリボナッチ数列は、フィボナッチ数列に次いでよく調べられている。0-fil型でオフセットが0番目からのものは
:
:
と表される。第0～21項の値は次の通りである：
:（OEIS ）
トリボナッチ数列の一般項は次で表される。
:T_n = \frac{\alpha^n}{(\alpha - \beta)(\alpha - \gamma)}+ \frac{\beta^n}{(\beta - \gamma)(\beta - \alpha)}+ \frac{\gamma^n}{(\gamma - \alpha)(\gamma - \beta)}
ただし、 は三次方程式  の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}（の虚立方根）
である。

また、上記の  を**トリボナッチ定数**という。これはフィボナッチ数列における黄金数に当たる定数で、トリボナッチ数列の隣接2項間の商はトリボナッチ定数に収束する：
:\lim_{n \to \infty} \frac{T_n}{T_{n-1}} = \alpha = 1.839286755214161\cdots

パスカルの三角錐の n 段目の三角形の数字を桂馬跳びに拾って合計すると 2n-1 個の数から成る数列ができる。この数列を上から三角形状に並べ、数字を桂馬跳びに拾って合計するとトリボナッチ数が現れる。
また  が十分に大きいとき、トリボナッチ数列の漸化式を遡らせると中間の三角形が現れ、桂馬跳びに同じ項が現れる。

T_n = T_{n-1}+T_{n-2}+T_{n-3} = T_{n-2}+2T_{n-3}+3T_{n-4}+2T_{n-5}+T_{n-6} = T_{n-3}+3T_{n-4}+6T_{n-5}+7T_{n-6}+6T_{n-7}+3T_{n-8}+T_{n-9}

#### テトラナッチ数
直前の四項の和に変更したテトラナッチ数列も同様に様々なことが知られている。同様にオフセット0番の 0-fil型は
:
:
と書けて、第0～21項の値は次の通りである：
: （OEIS ）
一般項は、四次方程式  の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, …（OEIS ）
この数列の一般項は
:L_n = \left( \frac{1+\sqrt{5}}{2} \right)^n + \left( \frac{1-\sqrt{5}}{2} \right)^n= \varphi^n + (1-\varphi)^n = {\varphi^n + (-\varphi)^{-n}}
と表される。

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

## 脚注

### 注釈

### 出典

## 参考文献
*
*
**
*
*
*
**
*
** Thomas Koshy：「フィボナッチ数・リュカ数大鑑（上）」、共立出版、ISBN 978-4-320-11588-0 (2025年8月27日).
*
** Thomas Koshy：「フィボナッチ数・リュカ数大鑑（下）」、共立出版、ISBN 978-4-320-11589-7 (2025年8月27日).
* - 『平方の書』の英訳。
* - 『算盤の書』の英訳。

## 関連項目

* 黄金比
* 数学定数
* 数列
* フィボナッチ数列の逆数和
* リュカ数
* リュカ数列
*ベンフォードの法則

## 外部リンク
* 
* 
* フィボナッチ数、トリボナッチ数、テトラナッチ数、ペンタナッチ数、ヘキサナッチ数 の考察
* 
* The Fibonacci Association（フィボナッチ協会）
* Fibonacci Quarterly Home Page（フィボナッチ・クォータリー）
* 日本フィボナッチ協会 第13回研究集会報告書2015年8月日本フィボナッチ協会 （リンク切れの場合はこちら）
* 日本フィボナッチ協会 第14回研究集会報告書2016年8月日本フィボナッチ協会 （リンク切れの場合はこちら）
* 日本フィボナッチ協会 第15回研究集会報告書2017年8月日本フィボナッチ協会 （リンク切れの場合はこちら）
* 日本フィボナッチ協会 第16回研究集会報告書2018年8月日本フィボナッチ協会
* 日本フィボナッチ協会 第17回研究集会報告書2019年8月日本フィボナッチ協会
* 日本フィボナッチ協会 第18回研究集会報告書2020年10月日本フィボナッチ協会
* 日本フィボナッチ協会 第19回研究集会報告書2021年10月日本フィボナッチ協会
* 日本フィボナッチ協会 第20回研究集会報告書2022年10月日本フィボナッチ協会
* 日本フィボナッチ協会 第21回研究集会報告書2023年11月日本フィボナッチ協会
* 日本フィボナッチ協会 第22回研究集会報告書2024年10月日本フィボナッチ協会
* 日本フィボナッチ協会 第23回研究集会報告書2025年10月日本フィボナッチ協会