フィボナッチ数列について

目次
理解
事例
コード
まとめ

【理解】フィボナッチ数列の解説
【事例】フィボナッチ数列の具体例
【コード】Pythonでフィボナッチ数列
まとめノート

【理解】フィボナッチ数列の解説

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

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

流れ

フィボナッチ数列の式
フィボナッチ数列の和の公式
フィボナッチ数列の極限
フィボナッチ数列の拡張

フィボナッチ数列の漸化式と一般項について

<漸化式>定義

$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 = \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$ から数列 $\{ a_n \}$ の一般項を導きなさい。

$a_{n+2} = a_{n+1} + a_n$ から $x^2 = x+1$ を考える。これを解くと $x=\frac{1+\sqrt{5}}{2}, \ \frac{1-\sqrt{5}}{2}$ となる。これらの値を $\alpha$, $\beta$ とする。

例題の漸化式は $$\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+2} - \alpha a_{n+1} = \beta (a_{n+1} - \alpha a_n)$ を計算すると $a_{n+2} = (\alpha + \beta) a_{n+1} - \alpha \beta a_n$ となる。

実際に $\alpha + \beta = 1$, $- \alpha \beta = 1$ である。

$b_n = a_{n+1} - \alpha a_{n}$ と置くと, $b_{n+1} = \beta b_n$ が成り立つ。ゆえに, 数列 $\{ b_n \}$ は初項 $b_1 = a_2 - \alpha a_1 $, 公比 $\beta$ の等比数列である。したがって, 次が成り立つ。

$$b_{n} = (a_2 - \alpha a_1) \cdot \beta^{n-1}.$$

$b_1 = a_2 - \alpha a_1$ $= 1 - \frac{1 + \sqrt{5}}{2} \cdot 1$ $=\frac{1 - \sqrt{5}}{2}$ $=\beta$.

$c_n = a_{n+1} - \beta a_{n}$ と置くと, $c_{n+1} = \alpha c_n$ が成り立つ。ゆえに, 数列 $\{ c_n \}$ は初項 $c_1 = a_2 - \beta a_1 $, 公比 $\alpha$ の等比数列である。したがって, 次が成り立つ。

$$c_{n} = (a_2 - \beta a_1) \cdot \alpha^{n-1}.$$

$c_1 = a_2 - \beta a_1$ $= 1 - \frac{1 - \sqrt{5}}{2} \cdot 1$ $=\frac{1 + \sqrt{5}}{2}$ $=\alpha$.

以上から, $b_n = a_{n+1} - \alpha a_n$, $c_n = a_{n+1} - \beta a_n$ であったから, 次の２式を得ることができる。

$$\begin{aligned} a_{n+1} - \alpha a_n &= \beta \cdot \beta^{n-1} \\ a_{n+1} - \beta a_n &= \alpha \cdot \alpha^{n-1} \end{aligned}$$

$a_{n+1}$ を消去するために下の式の両辺から上の式の両辺をそれぞれ引くと, $$-(\beta- \alpha)a_n = \alpha^n - \beta^n$$ となる。

$-(\beta - \alpha)$ $\displaystyle= -\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\}$ について $$F_1 + \ldots + F_n = F_{n+2} -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)+1}-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 \\
&=F_n + \ldots + F_1
\end{aligned}$$

である。

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

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

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

e.g. 具体的な観察。

$n=3$ のとき

① $F_1 + F_2 + F_3$

② $F_5 -1$

が同じ値の理由を観察します。

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

です。

①' $F_5$

②' $ F_3 + F_2 + F_1 + 1$

からそれぞれ $1$ を引けば, ①②ができます。

<公式>平方の和

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

証明はこちら

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

公式

フィボナッチ数列 $\{F_n\}$ について $$F_1^2 + \ldots + 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 + \ldots + F_k^2 = F_kF_{k+1}$ が成り立つと仮定する.

$n = k+1$ のときについて,

$$\begin{aligned}
F_{n}F_{n + 1} &= 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 + \ldots + F_1^2) \\
&= F_{k+1}^2 + \ldots + F_1^2 \\
&=F_n^2 + \ldots + F_1^2
\end{aligned}$$

である。

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

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

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

e.g. 公式の観察。

$n=3$ のとき,

① $F_1^2 + F_2^2 + F_3^2$

② $F_3F_4$

が等しい理由を観察します。

②について

$F_3F_4 = F_3(F_3+F_2)$ $= F_3^2+ F_2F_3$

です。$F_2F_3$ のところは

$F_2^2 + F_2F_1$

になります。 $F_2F_1$ のところは $F_2=F_1$ から, $F_1^2$ となります。

よって, ②は $F_3^2$ と $F_2^2$ と $F_1^2$ の和となり①と等しくなりました。

<公式>奇数項の和

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

証明はこちら

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

公式

フィボナッチ数列 $\{F_n\}$ について $$F_1 + F_3 + \ldots + F_{2n-1} = F_{2n}$$

証明.

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

$n=1$ のとき, 左辺は $F_1 = 1$ である. 右辺は $F_{2 \cdot 1} = 1$ である.

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

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

$n = k+1$ のときについて,

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

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

である.

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

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

e.g. 公式の観察。

$n=3$ のとき

① $F_1 + F_3 + F_5$

② $F_6$

が同じ理由を観察します。

①の $F_1$ は

$F_1 = F_2$.

①の $F_3$ は

$F_3 = F_4 - F_2$.

①の $F_5$ は

$F_5 = F_6- F_4$.

これらの和は $F_6$ で②と同じです。

<公式>偶数項の和

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

証明はこちら

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

公式

フィボナッチ数列 $\{F_n\}$ について $$F_2 + F_4 + \ldots + F_{2n} = F_{2n+1}-1$$

証明.

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

$n=1$ のとき, 左辺は $F_2 = 1$ である. 右辺は $F_{2 \cdot 1 +1}-1 = 2-1=1$ である.

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

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

$n = k+1$ のときについて,

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

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

である.

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

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

e.g. 公式の観察。

$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 \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\}$ について,

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

が成り立つ. ただし, $\displaystyle \phi = \frac{1 + \sqrt{5}}{2}$ である.

証明.

フィボナッチ数列の一般項の式（ビネーの公式）を利用して命題を示す.

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

フィボナッチ数列の比を計算する.

$\begin{aligned}
&\frac{F_{n+1}}{F_n} \\
&=\frac{ \frac{1}{\sqrt{5}} \left\{ \phi^{n+1} - \left(-\phi^{-1} \right)^{n+1} \right\}}{ \frac{1}{\sqrt{5}} \left\{ \phi^n - \left(-\phi^{-1} \right)^n \right\}}\\
&=\frac{\phi^{n+1} - \left(-\phi^{-1} \right)^{n+1}}{\phi^n - \left(-\phi^{-1} \right)^n} \\
&=\frac{\phi + \phi^{-1}(-\phi^{-2})^{n}}{1 - (-\phi^{-2} )^n}
\end{aligned}$

最後の計算は分母と分子を $\phi^n$ で割っている.

ここで, $0<\phi^{-2}<1$ であるから,

$\displaystyle \lim_{n \to \infty} (-\phi^{-2})^n = 0$

が成り立つ.

ゆえに, $\displaystyle \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \phi$ が成り立つ.

$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_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$

【事例】フィボナッチ数列の具体例

<総数>階段の上り方

$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)$$

解説はこちら

①の正方形の辺の長さを $1$ とすると, 以降の正方形の辺の長さはフィボナッチ数列となる。らせんの各パートの長さもフィボナッチ数列の規則で増えている。

［理由］$n$ 番目の辺の長さは, 前の２つの正方形の辺の長さの和になっていることが分かる。

正方形の辺の長さがフィボナッチ数列になっているので、らせんの各パートの長さもフィボナッチ数列の規則に従っている。

$n$ 番目の正方形内のらせんの長さは

$\displaystyle 2\pi F_n \times \frac{1}{4}$ $\displaystyle =\frac{\pi}{2} F_n$

である。

ゆえに, $n$ 番目までのらせんの長さの総和は

$\displaystyle \frac{\pi}{2} F_1 + \frac{\pi}{2} F_2 + \cdots + \frac{\pi}{2} F_n$ $\displaystyle =\frac{\pi}{2} ( F_1 + \cdots + F_n)$ $\displaystyle =\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でフィボナッチ数列

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

フィボナッチ数列 $\{a_n\}$ の値をPythonで出力してみよう。

Pythonコード

フィボナッチ数列の $a_1 = a_2=1$ を[1,1]としてリストを作る。例えばfibとする。

$2 \leq i <n$ としてfib[i-1]+fib[i-2]をforを用いて繰り返し.appendで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]} です。")

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

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

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

print(fib)

出力結果（コード２）

「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$

が成立する。

カテゴリー: 絵馬

タグ: 数列理科

【理解】フィボナッチ数列の解説

フィボナッチ数列の漸化式と一般項について

フィボナッチ数列の和の公式について

フィボナッチ数列の極限の性質について

フィボナッチ数列の拡張について

【事例】フィボナッチ数列の具体例

Memo

【コード】Pythonでフィボナッチ数列

まとめノート