フィボナッチ数列の公式整理ノート

表紙
基本
発展
現象
コード

フィボナッチ数列の公式整理ノート

このノートで

単元全体を分かりやすく整理しよう！

フィボナッチ数列の公式整理ノート
フィボナッチ数列が分かる
フィボナッチ数列を理解する
フィボナッチ数列の事例を観る
Pythonでフィボナッチ数列を作る

ノートの特徴

数学を勉強すると頭が混乱する人に公式を見やすく整理しました。

ノートの見方

タブレット・PCの利用を推奨

上部のタブ（タイトル下）を押すとトピックで区切って読めます。
目次を押すと好きな話題にジャンプできます。（タブで区切っててもジャンプできます。）
各公式の下の「証明はこちら」をクリックすると証明を詳しく読めます。

↑単元全体ページ

フィボナッチ数列が分かる

「フィボナッチ数列」とは

前の２つの数の和が次の数になる数列のこと。

記号

フィボナッチ数列を $\{ F_n \}$ とする。

<定義>漸化式

$F_n=\begin{cases}
1 & (n=1,2) \\
F_{n-1} + F_{n-2} & (n \geq 3)
\end{cases}$

詳細はこちら

<数列>フィボナッチ数列

$F_n=\{$ $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$, $89$, $144$, $233$, $377$, $\cdots$ $\}$

<一般項>ビネーの公式

$\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\}$

証明はこちら

フィボナッチ数列の漸化式 $a_{n+2} = a_{n+1} + a_n$, $a_1=a_2=1$ から一般項を導いてみよう。

ビネーの公式（フィボナッチ数列の一般項）

フィボナッチ数列 $\{a_n\}$ が漸化式 $a_{n+2} = a_{n+1} + a_n$ および $a_1=1, a_2=1$ で定義されるとき, その一般項は次の式で表される。 $$ a_n = \frac{1}{\sqrt{5}} \left\{ \left(\frac{1+\sqrt{5}}{2} \right)^n - \left(\frac{1-\sqrt{5}}{2} \right)^n \right\} $$

フィボナッチ数列の漸化式 $a_{n+2} = a_{n+1} + a_n$ から一般項を導く解法

$\displaystyle \alpha = \frac{1+\sqrt{5}}{2}$ と $\displaystyle \beta = \frac{1-\sqrt{5}}{2}$ によって, 漸化式を次の形に変形する:$$\begin{aligned} a_{n+2} - \alpha a_{n+1} &= \beta (a_{n+1} - \alpha a_n) \\ a_{n+2} - \beta a_{n+1} &= \alpha (a_{n+1} - \beta a_n) \end{aligned}$$
数列 $\{ a_{n+1} - \alpha a_{n} \}_n$ は初項 $a_2 - \alpha a_1 = \beta$, 公比 $\beta$ の等比数列と認識でき, $a_{n+1} - \alpha a_n$ $= \beta \cdot \beta^{n-1}$ が得られる.
数列 $\{ a_{n+1} - \beta a_{n} \}_n$ は初項 $a_2 - \beta a_1 = \alpha$, 公比 $\alpha$ の等比数列と認識でき, $a_{n+1} - \beta a_n$ $=\alpha \cdot \alpha^{n-1}$ が得られる.
(2)の式 $a_{n+1} - \alpha a_n$ $=\beta^{n}$ と(3)の式 $a_{n+1} - \beta a_n$ $=\alpha^{n}$ から $a_{n+1}$ を消去することで $a_n$ $\displaystyle =\frac{1}{\alpha - \beta}(\alpha^n-\beta^n)$ を導く.

導出：特性方程式による一般項の決定

漸化式 $a_{n+2} = a_{n+1} + a_n$ ($a_1=a_2=1$) を解くために, 特性方程式 $x^2 = x+1$ を考える。その解を $\alpha = \frac{1+\sqrt{5}}{2}, \beta = \frac{1-\sqrt{5}}{2}$ とする。

§等比数列への変形

与えられた漸化式は, 次の2つの等比数列の形に変形できる。 $$ \begin{aligned} (1)\quad a_{n+1} - \alpha a_n &= \beta(a_{n} - \alpha a_{n-1}) \\ (2)\quad a_{n+1} - \beta a_n &= \alpha(a_{n} - \beta a_{n-1}) \end{aligned} $$

§各数列の一般項

(1)より, 数列 $\{a_{n+1} - \alpha a_n\}$ は初項 $a_2 - \alpha a_1$, 公比 $\beta$ の等比数列である。初項は $1 - \alpha = \beta$ であるから, $$ a_{n+1} - \alpha a_n = \beta \cdot \beta^{n-1} = \beta^n \quad \cdots ① $$ 同様に, (2)より初項 $a_2 - \beta a_1 = 1 - \beta = \alpha$ であるから, $$ a_{n+1} - \beta a_n = \alpha \cdot \alpha^{n-1} = \alpha^n \quad \cdots ② $$

§$a_n$ の算出

②式から①式を引いて $a_{n+1}$ を消去すると： $$ \begin{aligned} (\alpha - \beta)a_n &= \alpha^n - \beta^n \\ a_n &= \frac{\alpha^n - \beta^n}{\alpha - \beta} \end{aligned} $$ ここで, $\alpha - \beta = \frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2} = \sqrt{5}$ である。

§結論

求めた値を代入すると, フィボナッチ数列の一般項が得られる。 $$ a_n = \frac{1}{\sqrt{5}} \left\{ \left(\frac{1+\sqrt{5}}{2} \right)^n - \left(\frac{1-\sqrt{5}}{2} \right)^n \right\} $$

$\alpha = \frac{1 + \sqrt{5}}{2}$ と $\beta = \frac{1 - \sqrt{5}}{2}$ とすると, $\alpha + \beta =1$, $\alpha \beta =-1$, $\alpha - \beta = \sqrt{5}$ である。
このとき,
$a_1$ $= \frac{1}{\sqrt{5}} (\alpha -\beta )$ $= \frac{1}{\sqrt{5}} \cdot \sqrt{5}$ $=1.$
$a_2$ $= \frac{1}{\sqrt{5}} (\alpha^2 -\beta^2 )$ $= \frac{1}{\sqrt{5}} (\alpha - \beta)(\alpha + \beta)$ $=1.$
$a_3$ $= \frac{1}{\sqrt{5}} (\alpha^3 -\beta^3 )$ $= \frac{1}{\sqrt{5}} (\alpha - \beta)$ $\{(\alpha + \beta)^2 - \alpha \beta \}$ $=2.$

<公式>フィボナッチ数列の和

$\displaystyle \sum_{k=1}^nF_k = F_{n+2}-1$

証明はこちら

フィボナッチ数列の初項から第 $n$ 項までの和が $F_{n+2}-1$ であることを証明してみよう。

フィボナッチ数列の和

フィボナッチ数列 $\{F_n\}$ に対して, 任意の正の整数 $n$ について次が成り立つ。 $$ F_1 + \cdots + F_n = F_{n+2} - 1 $$

数学的帰納法による証明

数学的帰納法によって示す。

§$n=1$ のとき

$n=1$ のとき, 左辺は $F_1 = 1$ である。右辺は $F_3 - 1 = 2 - 1 = 1$ である。

ゆえに, $n=1$ のとき, 示すべき等式は成り立つ。

§帰納法の仮定

$n = k \in \mathbb{N}$ のとき, $$ F_1 + \ldots + F_k = F_{k+2} - 1 $$ が成り立つと仮定する。

§帰納法の推論

$n = k+1$ のときについて考える。

$$ \begin{aligned} F_{n+2} - 1 &= F_{(k+1)+2} - 1 \\ &= F_{k+3} - 1 \\ &= F_{k+2} + F_{k+1} - 1 \\ &= F_{k+1} + (F_{k+2} - 1) \\ &= F_{k+1} + (F_k + \ldots + F_1) \\ &= F_{k+1} + \ldots + F_1 \end{aligned} $$

したがって, $n = k+1$ のときも, $$ F_1 + \ldots + F_n = F_{n+2} - 1 $$ が成り立つ。

フィボナッチ数列 $\{F_n\}$ は $$ F_{k+3} = F_{k+2} + F_{k+1} $$ を満たす。

§結論

以上から, 数学的帰納法によって, 任意の自然数 $n$ について $$ F_1 + \ldots + F_n = F_{n+2} - 1 $$ が成り立つ。

例えば, $n=3$ のときについて考える。
① $F_1 + F_2 + F_3$
② $F_5 - 1$
が同じ値になる理由を観察する。まず, $F_5$ を分解すると $$ \begin{aligned} F_5 &= F_3 + F_4 \\ &= F_3 + (F_2 + F_3) \\ &= F_3 + F_2 + (F_1 + F_2) \\ &= F_3 + F_2 + F_1 + 1 \end{aligned} $$ よって,
①' $F_5$
②' $F_3 + F_2 + F_1 + 1$
から, それぞれ $1$ を引けば, ① $F_1 + F_2 + F_3$ と ② $F_5 - 1$ が得られる。
したがって, $n=3$ のとき, $$ F_1 + F_2 + F_3 = F_5 - 1 $$ が確かに成り立つことが分かる。

<性質>比の極限

$\displaystyle \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \frac{1 + \sqrt{5}}{2}$

証明はこちら

フィボナッチ数列の比の極限が黄金比 $\displaystyle \phi = \frac{1 + \sqrt{5}}{2}$ $\fallingdotseq 1.618$ に収束することを証明してみよう。

命題（フィボナッチ数列の隣接項の比の収束）

フィボナッチ数列 $\{F_n\}$ について, 隣接する項の比は $n$ を無限大に大きくするとき, 黄金比 $\phi$ に収束する。 $$ \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \phi $$ ただし, $\phi = \frac{1 + \sqrt{5}}{2} \approx 1.618$ である。

$F_2/F_1$ $=1$,
$F_3/F_2$ $=2$,
$F_4/F_3$ $=1.5$,
$F_5/F_4 \fallingdotseq1.66$,
$F_6/F_5 =1.6$,
$F_7/F_6 =1.625$,
$F_8/F_7 \fallingdotseq1.615$,

ビネーの公式を利用して, $\frac{F_{n+1}}{F_n} \to \phi$ を示す。ここで $\phi = \frac{1+\sqrt{5}}{2}$ とおくと, $\frac{1-\sqrt{5}}{2} = - \phi^{-1}$ である。ビネー公式は $F_n = \frac{1}{\sqrt{5}} \{ \phi^n - (-\phi^{-1})^n \}$ と表される。

§比の計算

$$ \begin{aligned} \frac{F_{n+1}}{F_n} &= \frac{\phi^{n+1} - (-\phi^{-1})^{n+1}}{\phi^n - (-\phi^{-1})^n} \\[10pt] &= \frac{\phi^n \cdot \phi - \phi^n \cdot (-\phi^{-1})(-\phi^{-2})^n}{\phi^n \{ 1 - (-\phi^{-2})^n \}} \end{aligned} $$ 分母と分子を $\phi^n$ で割ると, 次のようになる。 $$ \frac{F_{n+1}}{F_n} = \frac{\phi - (-\phi^{-1})(-\phi^{-2})^n}{1 - (-\phi^{-2})^n} $$

§極限の計算

ここで, $|-\phi^{-2}| = | \frac{1-\sqrt{5}}{1+\sqrt{5}} | < 1$ である。よって $n \to \infty$ のとき, $$ \lim_{n \to \infty} (-\phi^{-2})^n = 0 $$ となる。これより, $$ \begin{aligned} \lim_{n \to \infty} \frac{F_{n+1}}{F_n} &= \frac{\phi - (-\phi^{-1}) \cdot 0}{1 - 0} \\[5pt] &= \phi \end{aligned} $$ が導かれる。

フィボナッチ数列を理解する

定義の拡張について

<再定義>フィボナッチ数列

$F_n=
\begin{cases}
0 & (n=0) \\
1 & (n=1) \\
F_{n-1} + F_{n-2} & (n \geq 2)
\end{cases}$

こんな数列になる

$0$, $1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$, $\cdots$

<定義>トリボナッチ数列

$F_n=F_{n-1} + F_{n-2} +F_{n-3}$ $(n \geqq 3)$,

$F_0 =F_1= 0$, $F_2 = 1$

こんな数列になる

$0$ , $0$, $1$, $1$, $2$, $4$, $7$, $13$, $24$, $44$, $81$, $149$, $\cdots$

<定義>テトラナッチ数列

$F_n=F_{n-1} + F_{n-2} +F_{n-3} + F_{n- 4}$ $(n \geqq 4)$,

$F_0 =F_1= F_2 = 0$, $F_3 = 1$

こんな数列になる

$0$ , $0$, $0$, $1$, $1$, $2$, $4$, $8$, $15$, $29$, $56$, $108$, $208$, $\cdots$

数列の和の公式について

<公式>フィボナッチ数列の和

$\displaystyle \sum_{k=1}^nF_k = F_{n+2}-1$

証明はこちら

フィボナッチ数列の初項から第 $n$ 項までの和が $F_{n+2}-1$ であることを証明してみよう。

フィボナッチ数列の和

フィボナッチ数列 $\{F_n\}$ に対して, 任意の正の整数 $n$ について次が成り立つ。 $$ F_1 + \cdots + F_n = F_{n+2} - 1 $$

数学的帰納法による証明

数学的帰納法によって示す。

§$n=1$ のとき

$n=1$ のとき, 左辺は $F_1 = 1$ である。右辺は $F_3 - 1 = 2 - 1 = 1$ である。

ゆえに, $n=1$ のとき, 示すべき等式は成り立つ。

§帰納法の仮定

$n = k \in \mathbb{N}$ のとき, $$ F_1 + \ldots + F_k = F_{k+2} - 1 $$ が成り立つと仮定する。

§帰納法の推論

$n = k+1$ のときについて考える。

したがって, $n = k+1$ のときも, $$ F_1 + \ldots + F_n = F_{n+2} - 1 $$ が成り立つ。

フィボナッチ数列 $\{F_n\}$ は $$ F_{k+3} = F_{k+2} + F_{k+1} $$ を満たす。

§結論

以上から, 数学的帰納法によって, 任意の自然数 $n$ について $$ F_1 + \ldots + F_n = F_{n+2} - 1 $$ が成り立つ。

<公式>平方の和

$\displaystyle \sum_{k=1}^nF_k^2 = F_nF_{n+1}$

証明はこちら

フィボナッチ数列の初項から第 $n$ 項までの平方和が $F_nF_{n+1}$ であることを証明してみよう。

命題（フィボナッチ数列の平方和）

フィボナッチ数列 $\{F_n\}$ に対して，任意の自然数 $n$ について, $$ F_1^2 + F_2^2 + \cdots + F_n^2 = F_n F_{n+1} $$ が成り立つ。

フィボナッチ数列の平方和

フィボナッチ数列 $\{F_n\}$ を $F_1 =F_2= 1$ かつ $$F_{n+2}=F_{n+1}+F_n$$ によって定める。これに対し, $$F_1^2+\cdots+F_n^2 = F_nF_{n+1}$$ が成り立つことを数学的帰納法によって示す。

§初期条件の確認

$n=1$ のとき, 左辺は $F_1^2 = 1$ である。一方, 右辺は $$F_1F_2 = 1\cdot 1 = 1$$ である。よって, $n=1$ のとき, 示すべき等式は成り立つ。

§帰納法の仮定

$n=k \in \mathbb{N}$ のとき, $$F_1^2+\cdots+F_k^2 = F_kF_{k+1}$$ が成り立つと仮定する。

§帰納法の推論

$n=k+1$ のときについて考える。フィボナッチ数列の定義より $$F_{k+2}=F_{k+1}+F_k$$ が成り立つから,

$$\begin{aligned} F_{k+1}F_{k+2} &= F_{k+1}(F_{k+1}+F_k) \\ &= F_{k+1}^2 + F_kF_{k+1} \\ &= F_{k+1}^2 + (F_k^2+\cdots+F_1^2) \\ &= F_{k+1}^2+\cdots+F_1^2 \end{aligned}$$

よって, $n=k+1$ のときも, 示すべき等式は成り立つ。

§結論

以上より, 数学的帰納法によって, 任意の自然数 $n$ について $$F_1^2+\cdots+F_n^2 = F_nF_{n+1}$$ が成り立つ。

$n=3$ のとき，
① $F_1^2 + F_2^2 + F_3^2$
② $F_3 F_4$
が等しくなる理由を観察します。

②について考えると， $$ F_3 F_4 = F_3 (F_3 + F_2) = F_3^2 + F_2 F_3 $$ です。

ここで， $$ F_2 F_3 = F_2 (F_2 + F_1) = F_2^2 + F_2 F_1 $$ となります。

さらに，$F_2 = F_1$ であるから， $F_2 F_1 = F_1^2$ です。

以上より， $$ F_3 F_4 = F_3^2 + F_2^2 + F_1^2 $$ となり，①と②は等しいことが分かります。

<公式>奇数項の和

$\displaystyle \sum_{k=1}^nF_{2k-1}= F_{2n}$

証明はこちら

奇数番号のフィボナッチ数の和 $ F_1 + F_3 + F_5 + \cdots + F_{2n-1}$ が $F_{2n}$ であることを証明してみよう。

公式（フィボナッチ数列の奇数項の和）

フィボナッチ数列 $\{F_n\}$ （ただし $F_1=F_2=1$）について, 次が成り立つ。 $$ \sum_{k=1}^n F_{2k-1} = F_{2n} $$

数学的帰納法による証明

任意の自然数 $n$ について, 次の等式(＊)が成り立つことを数学的帰納法で証明する。 $$ F_1 + F_3 + \cdots + F_{2n-1} = F_{2n}$$

§$n=1$ のとき

左辺は $F_1 = 1$, 右辺は $F_{2 \cdot 1} = F_2 = 1$ である。
ゆえに, $n=1$ のとき等式(＊)は成り立つ。

§$n=k$ のときを仮定

$n=k$ のとき, 等式(＊)が成り立つと仮定する。すなわち, $$ F_1 + F_3 + \cdots + F_{2k-1} = F_{2k} $$ が成り立つと仮定する。

§$n=k+1$ のとき

$n=k+1$ のとき, (＊)の左辺の和を計算すると： $$ \begin{aligned} &(F_1 + \cdots + F_{2k-1}) + F_{2k+1} \\ &= F_{2k} + F_{2k+1}\\ &= F_{2k+2} \\ &= F_{2(k+1)} \end{aligned} $$ となり, $n=k+1$ のときの右辺に一致する。
※ ここでフィボナッチ数列の定義 $F_{2k+2} = F_{2k+1} + F_{2k}$ を用いた。

§結論

よって, $n=k$ のとき等式が成り立つと仮定すると, $n=k+1$ のときも成り立つことが示された。
数学的帰納法により, すべての自然数 $n$ について $$ F_1 + F_3 + \cdots + F_{2n-1} = F_{2n} $$ は成り立つ。

公式の観察； $n=3$ のとき, ① $F_1 + F_3 + F_5$ と ② $F_6$ が同じ理由を観察します。

$F_1$ は $F_2$ と等しく, $F_3$ は $F_4 - F_2$ と等しく, $F_5$ は $F_6- F_4$ と等しいです。これらの和は $F_6$ になり, ②と一致します。

<公式>偶数項の和

$\displaystyle \sum_{k=1}^nF_{2k}= F_{2n+1}-1$

証明はこちら

偶数番号のフィボナッチ数の和 $F_2 + F_4 + \cdots + F_{2n}$ が $F_{2n+1}-1$ であることを証明してみよう。

公式（フィボナッチ数列の偶数項の和）

フィボナッチ数列 $\{F_n\}$ (ただし $F_1=F_2=1$) について, 次が成り立つ。 $$\sum_{k=1}^n F_{2k} = F_{2n+1} - 1$$

数学的帰納法による証明

すべての自然数 $n$ について, 次の等式(＊)が成り立つことを数学的帰納法で証明する。 $$ F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1$$

§$n=1$ のとき

左辺は $F_2 = 1$ である。
右辺は $F_{2 \cdot 1 + 1} - 1 = F_3 - 1 = 2 - 1 = 1$ である。
ゆえに, $n=1$ のとき等式(＊)は成り立つ。

§$n=k$ のときを仮定

$n=k$ のとき, 等式(＊)が成り立つと仮定する。すなわち, $$ F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1 $$ が成り立つとする。

§$n=k+1$ のとき

$n=k+1$ のとき, 左辺の和を計算すると次のようになる。 $$ \begin{aligned} &(F_2 + F_4 + \cdots + F_{2k}) + F_{2k+2} \\[5pt] &= (F_{2k+1} - 1) + F_{2k+2} \\[5pt] &= (F_{2k+2} + F_{2k+1}) - 1 \\[5pt] &= F_{2k+3} - 1 \\[5pt] &= F_{2(k+1)+1} - 1 \end{aligned} $$ となり, $n=k+1$ のときも等式(＊)は成り立つ。

§結論

以上より, 数学的帰納法によって, すべての自然数 $n$ について $$ F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1 $$ が成り立つ。

公式の観察； $n=3$ のとき ① $F_2 + F_4 + F_6$ と ② $F_7 - 1$ が同じ値の理由を観察します。

①について $F_2 = F_3 - F_1$, $F_4 = F_5 - F_3$, $F_6 = F_7- F_5$ と変形して和をとると, $F_7 -F_1$ となる。 $F_1=1$ だから, ①と②は同じ値と分かる。

<公式>交代和

$\displaystyle \sum_{k=1}^n (-1)^{k+1} F_k = (-1)^{n+1}F_{n-1}+1$

多項間の関係について

<漸化式>関係式①

$F_nF_{n+3} = F_{n+2}^2 - F_{n+1}^2$

<漸化式>関係式②

$F_nF_{n+3} = F_{n+1}F_{n+2} + (-1)^{n+1}$

<漸化式>関係式③

$F_{n-1}F_{n+1} - F_n^2 = (-1)^n$

<漸化式>関係式④

$F_{m+n} = F_{m+1}F_n + F_mF_{n-1}$

極限の性質について

<性質>比の極限

$\displaystyle \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \frac{1 + \sqrt{5}}{2}$

証明はこちら

フィボナッチ数列の比の極限が黄金比 $\displaystyle \phi = \frac{1 + \sqrt{5}}{2}$ $\fallingdotseq 1.618$ に収束することを証明してみよう。

命題（フィボナッチ数列の隣接項の比の収束）

$F_2/F_1$ $=1$,
$F_3/F_2$ $=2$,
$F_4/F_3$ $=1.5$,
$F_5/F_4 \fallingdotseq1.66$,
$F_6/F_5 =1.6$,
$F_7/F_6 =1.625$,
$F_8/F_7 \fallingdotseq1.615$,

§比の計算

§極限の計算

<性質>逆数和の極限

$\displaystyle \sum_{n =1}^{\infty} \frac{1}{F_n} = 3.35998 \cdots$（無理数）

整数的な性質について

<性質>偶数の条件

$F_m$ が偶数である $\Leftrightarrow$ $m$ が $3$ の倍数である

<性質> $5$ の倍数である条件

$F_m$ が $5$ の倍数である $\Leftrightarrow$ $m$ が $5$ の倍数である

<性質> $8$ の倍数である条件

$F_{6m}$ は $8$ の倍数である。

<性質>最大公約数の対応

$p,q \in \mathbf{N}$ の最大公約数が $r$ ならば, $F_p$ と $F_q$ の最大公約数は $F_r$ である。

<性質>互いに素の性質

連続する2つのフィボナッチ数は互いに素である。

フィボナッチ数列の事例を観る

<総数>階段の上り方

$n$ 段の上り方の総数は $F_{n+1}$

解説はこちら

階段を１段か２段で上るときの上り方の総数は, 階段の段数に関してフィボナッチ数となる。$n$ 段の階段の上り方の総数を $a_n$ 通りとする。

［1段のとき］上り方は1通りだけ。$(a_1=1)$

［2段のとき］上り方は2通りある。$(a_2=2)$

$n$ 段のときは, 最後に1段上るか, 2段上るかで場合分けする。

最後に1段上るときは, それ以前に $n-1$ 段上っておく必要がある。つまり, $a_{n-1}$ 通りの上り方があって,そのどの場合も最後は1段上ることになる。

一方で, 最後に2段上るときは,それ以前に $n-2$ 段上っておく必要がある。つまり, $a_{n-2}$ 通りの上り方があって,そのどの場合も最後は2段上ることになる。

したがって, $a_n=a_{n-1}+a_{n-2}$ が成り立つ。$a_1=1$, $a_2=2$ であるから, $a_n = F_{n+1}$ が成り立つ.

<総数>タイルの敷き詰め方

タイルの敷き詰め方の総数は $F_{n+1}$

解説はこちら

$2$ cm× $n$ cmの長方形がある。ここに, $2$ cm× $1$ cmのブロックAをピッタリと敷き詰める方法の総数を $a_n$ 通りとする。

［ $n=1$ ］$2$ cm× $1$ cmの長方形にブロックAを敷き詰める方法は1通りだけ。$(a_1=1)$

［ $n=2$ ］$2$ cm× $2$ cmの長方形にブロックAを敷き詰める方法は縦に詰めるか横に詰めるかの2通りだけ。$(a_2=2)$

$2$ cm×$n$ cmの長方形にブロックAを敷き詰めるとき端にブロックAを縦に１つはめるか, ２つのブロックを横にして正方形にしてはめるかで場合分けする。

最後にブロックAを縦に１つはめるときは, 残りの部分が $2$ × $n-1$ の長方形にブロックAを敷き詰める必要がある。つまり, $a_{n-1}$ 通りの敷き詰め方があって, そのどの場合も最後はブロックAを１つはめることになる。

一方でブロックAを横に２つにして正方形をはめるときは, 残りの部分が $2$ × $n-2$ の長方形にブロックAを敷き詰める必要がある。つまり, $a_{n-2}$ 通りの敷き詰め方があって, そのどの場合も最後はブロックAを２つ横の正方形にしてはめることになる。

したがって, $a_n=a_{n-1}+a_{n-2}$ が成り立つ。$a_1=1$, $a_2=2$ であるから, $a_n = F_{n+1}$ が成り立つ。

<長さ>フィボナッチ螺旋

$n$ 番目までのらせんの長さは $$\displaystyle \frac{\pi}{2}(F_{n+2}-1)$$

解説はこちら

正方形で描けるフィボナッチ螺旋（黄金螺旋）の長さがフィボナッチ数列で表せることを示してみよう。

性質（フィボナッチ螺旋）

$n$ 番目の正方形内に描かれる四分円弧の半径を $F_n$ とする。①と②の正方形の辺の長さは $1$ とする。

数列 $\{F_n\}$ はフィボナッチ数列となり, その弧の長さ $L_n$ は $$ L_n = \frac{\pi}{2} F_n$$ となり, また, 初めから $n$ 番目までの曲線の全長 $S_n$ は $$ S_n = \frac{\pi}{2}(F_{n+2} - 1)$$ の式で表される。

例えば, ①と②の円弧の長さはそれぞれ $\frac{\pi}{2}\times 1$ です。③では $\frac{\pi}{2}\times 2$, ④では $\frac{\pi}{2}\times 3$, ⑤では $\frac{\pi}{2}\times 5$, ⑥では $\frac{\pi}{2}\times 8$ です。①〜⑥の曲線の長さは $10 \pi$ です！

また, 2つの式は次の形になります： $$ \begin{aligned} L_n &= \frac{\pi}{2\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\} \\ S_n &= \frac{\pi}{2\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^{n+2} - \left( \frac{1-\sqrt{5}}{2} \right)^{n+2} \right\} - \frac{\pi}{2} \end{aligned}$$

導出：黄金螺旋の構造と累計の長さ

§$F_n$ がフィボナッチ数列であること

黄金螺旋は, 正方形を「渦巻き状」に隣接させていくことで作られる。新しい正方形の一辺の長さは, 常に「直前の正方形」と「その一つ前の正方形」の一辺を合わせた長さになる。

$n$ 番目の正方形の辺の長さを $F_n$ とすると, 図形的な配置から $F_n = F_{n-1} + F_{n-2}$ という関係が生まれる。

§各円弧の長さ $L_n$

$n$ 番目の正方形内に描かれる四分円の半径は $F_n$ である。したがって, その円弧の長さ $L_n$ は円周の $1/4$ となり, 次のように表される。 $$ L_n = 2\pi F_n \times \frac{1}{4} = \frac{\pi}{2}F_n $$

§全長の計算とビネーの公式

$n$ 番目までの全長の和 $S_n$ は, 和の性質 $\sum_{k=1}^n F_k = F_{n+2} - 1$ より, $$ S_n = \sum_{k=1}^n \frac{\pi}{2} F_k = \frac{\pi}{2}(F_{n+2} - 1) $$ となる。

<性質>パスカルの三角形

$\displaystyle F_{n+1} = \sum_{k=0}^{[\frac{n}{2}]}{}_{n-k} \mathrm{C}_k$

証明はこちら

パスカルの三角形である直線上にある数の和をとっていくとフィボナッチ数列になることを理解してみよう。

性質（パスカルの三角形とフィボナッチ数列）

$n \geq 0$ とする。フィボナッチ数列 $\{F_n\}$ （ただし $F_1=F_2=1$）について, 次の等式が成り立つ。 $$ F_{n+1} = \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} {}_{n-k}\mathrm{C}_k $$ 等式の右辺は, パスカルの三角形（下図）において, 上から $n$ 本目 $(n \geq 0)$ の直線状の数の和に対応している。

直線上の数の和は上から $1$, $1$, $1+1=2$, $1+2=3$, $1+3+1=5$, $1+4+3=8$, $1+5+6+1=13$ です。フィボナッチ数列が現れています。

フィボナッチ数列と二項係数の和の等式

$\displaystyle a_n = \sum_{k=0}^{\lfloor n/2 \rfloor} {}_{n-k}\mathrm{C}_k$ とおき, これがフィボナッチ数列の定義 $a_n = a_{n-1} + a_{n-2}$ および $a_1 = a_2 = 1$ を満たすことを示す。

§初期条件の確認

$n=0$ のとき, $a_0 = {}_{0}\mathrm{C}_0 = 1 = F_1$
$n=1$ のとき, $a_1 = {}_{1}\mathrm{C}_0 = 1 = F_2$
となり, フィボナッチ数列の初期条件と一致する。

§パスカルの三角形における直線の意味

ある直線上の $k$ 番目の数を ${}_{n-k}\mathrm{C}_k$ とすると, 次の数は段を1つ下げ（$n$を増やす）, 右へ1つずらす（$k$を増やす）ことで得られる。このとき, 二項係数が定義される条件 $n-k \geq k$ より $k \leq n/2$ が導かれ, $\displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} {}_{n-k}\mathrm{C}_k$ はパスカルの三角形を斜めに結んだ数の和であることが確認できる。

以下, $n \geq 2$ として, $a_{n} = a_{n-1} + a_{n-2}$ であることを示す。

§漸化式の確認 ($n$ が偶数の場合)

$n$ が偶数の場合, $\ell$ を整数として $n=2 \ell$ とする. このとき,
$\begin{aligned} a_n &=\displaystyle \sum_{k=0}^{\ell}{}_{2\ell-k} \mathrm{C}_k \\ &\displaystyle = {}_{2\ell}\mathrm{C}_0 +\sum_{k=1}^{\ell-1}{}_{2\ell-k} \mathrm{C}_k+{}_{\ell} \mathrm{C}_\ell \\ & \displaystyle = 2 +\sum_{k=1}^{\ell-1}{}_{2\ell-k} \mathrm{C}_k \end{aligned}$
$\begin{aligned} a_{n-1} & \displaystyle =\sum_{k=0}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k \\ & \displaystyle ={}_{2\ell-1}\mathrm{C}_0+\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k \\ &\displaystyle =1+\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k \end{aligned}$
$\begin{aligned} a_{n-2} & \displaystyle =\sum_{k=0}^{\ell-1}{}_{(2\ell-2)-k} \mathrm{C}_k \\ &\displaystyle =\sum_{k=1}^{\ell}{}_{(2\ell-2)-(k-1)} \mathrm{C}_{k-1} \\ & \displaystyle =\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_{k-1}+{}_{\ell-1} \mathrm{C}_{\ell-1} \\ & \displaystyle =\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_{k-1}+1 \end{aligned}$
である。 $a_{n-1}+a_{n-2}$ を計算すると,
$\displaystyle 1+\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k$ $\displaystyle +\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_{k-1}+1$ $=\displaystyle 2+\sum_{k=1}^{\ell-1} \{{}_{(2\ell-1)-k}\mathrm{C}_k +{}_{(2\ell-1)-k} \mathrm{C}_{k-1} \}$
となる。関係式 $${}_n\mathrm{C}_r +{}_n\mathrm{C}_{r+1} = {}_{n+1}\mathrm{C}_{r+1}$$ を利用して, さらに計算すると, $$\displaystyle 2+\sum_{k=1}^{\ell-1} {}_{2\ell-k}\mathrm{C}_k$$ となり, $a_n$ の式と等しいことが分かる。

§漸化式の確認 ($n$ が奇数の場合)

$n$ が奇数の場合も同様に $a_n = a_{n-1} + a_{n-2}$ が成り立つ。

§結論

ゆえに, $a_n$ はフィボナッチ数列の定義 $a_n = a_{n-1} + a_{n-2}$ および初期値 $a_0=1, a_1=1$ を満たす。したがって, $a_n = F_{n+1}$ が成り立つ。

Memo

<Memo>$\pi$ の連分数展開

$\displaystyle \pi = 3 + \frac{1^2}{6 + \frac{3^2}{6+\frac{5^2}{\cdots}}}$

<Memo>一山崩し

一山崩しというゲームの必勝法にフィボナッチ数が関係するそう。

<Memo>株価💰

フィボナッチリトレースメント
(参照リンク)

<Memo>うさぎ🐇

うさぎのつがい数(参照リンク)

<写真のみ>ロマネスコ

もっと写真

Pythonでフィボナッチ数列を作る

<出力>フィボナッチ数列

fib = [1, 1]

for i in range(2, n):
  fib.append(fib[i-1]+fib[i-2])

コードはこちら

フィボナッチ数列をPythonで出力してみよう。

Python

フィボナッチ数列をリストfibとして作成する。
(1) リストをfib=[1,1]とする。
(2) iを $2$ から $n-1$ までの数として, fib[i-1]+fib[i-2]を fib に繰り返し追加する。

入力例①. $n$ 番目のフィボナッチ数を出力する

n = int(input("何番目のフィボナッチ数を出力しますか？: "))
fib = [1, 1]

for i in range(2, n):
    fib.append(fib[i - 1] + fib[i - 2])

print(f"{n} 番目のフィボナッチ数は {fib[n-1]} です。")

RESULT / OUTPUT

「55」と出力される。

入力例②. $n$ 番目までのフィボナッチ数を出力する

n = int(input(何番目までのフィボナッチ数を出力しますか？:))
fib = [1, 1]

for i in range(2, n):
  fib.append(fib[i - 1] + fib[i - 2])
print(fib)

RESULT / OUTPUT

「10」と入力した。

まとめノート

「フィボナッチ数列」とは

前の２つの数の和が次の数になる数列のこと。

定義

任意の自然数 $n$ について,

$F_{n+2} = F_{n+1} + F_n$

, $F_1=F_2=1$.

数列

$1$, $1$, $2$, $3$, $5$, $8$, $13$, $21$, $34$, $55$, $89$, $144$, $\cdots$

A. 一般項（Binetの公式）

$F_n = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\}$

B. フィボナッチ数列の多項間の性質

$F_1 + F_2 + \cdots + F_n = F_{n+2}-1$
$F_1 + F_3 + \cdots + F_{2n-1} = F_{2n}$, $F_2 + F_4 + \cdots + F_{2n} = F_{2n+1}-1$
$F_1^2 + F_2^2 + \cdots + F_n^2 = F_{n}F_{n+1}$
$F_1 - F_2 + \cdots + (-1)^{n+1}F_n = (-1)^{n+1}F_{n-1}+1$
$F_{n-1}F_{n+1} - F_n^2 = (-1)^n$
$F_{m+n} = F_{m+1}F_n + F_mF_{n-1}$

C. フィボナッチ数列の整数的な性質

$p,q \in \mathbf{N}$ の最大公約数が $r$ ならば, $F_p$ と $F_q$ の最大公約数は $F_r$ である
連続する2つのフィボナッチ数は互いに素である

ポイント解説

$\phi = \frac{1+\sqrt{5}}{2}$ とする。特性方程式 $x^2=x+1$ の解 $\phi$ と $-\phi^{-1}$ から,

$$\left\{ \begin{aligned}
&a_{n+1} - \phi a_n = (-\phi^{-1})^n\\
&a_{n+1} - (-\phi^{-1}) a_n = \phi^n
\end{aligned} \right.$$

が成り立ち一般項が導出される。なお, この式から隣り合う２項の比の極限

$\displaystyle \lim_{n \to \infty} F_{n+1}/F_n = \phi$

も分かる。

以下の関係式も成立する：

$F_nF_{n+3} = F_{n+2}^2 - F_{n+1}^2$
$F_nF_{n+3} = F_{n+1}F_{n+2} + (-1)^{n+1}$

以下も成立する：

$F_m$ が偶数 $\Leftrightarrow$ $m$ が $3$ の倍数
$F_m$ が $5$ の倍数 $\Leftrightarrow$ $m$ が $5$ の倍数
$F_{6m}$ は $8$ の倍数

黄金螺旋

$n$ 番目の円弧の長さ $A_n$ について,

$A_{n+2} = A_{n+1} + A_n$

が成立する。

終わり

カテゴリー: 絵馬

タグ: 数列理科

フィボナッチ数列の公式整理ノート