- まとめ
- 具体例
「フィボナッチ数列」とは
前の2つの数の和が次の数になる数列のこと。
定義
任意の自然数 $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\}$ $= \frac{1}{\sqrt{5}}\{ \phi^n - (1-\phi)^n \}$
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つのフィボナッチ数は互いに素である
ポイント解説
A
黄金数 $\frac{1+\sqrt{5}}{2}$ を $\phi$ とする. 特性方程式 $x^2=x+1$ の解 $\phi$ と $1-\phi$ により,
$$\left\{ \begin{array}{ll}
a_{n+1} - \phi a_n &= (1-\phi)^n\\
a_{n+1} - (1-\phi) a_n &= \phi^n
\end{array} \right. $$
が成り立つことから, Binetの公式が導出される. なお, この式から隣り合う2項の比の極限
$\displaystyle \lim_{n \to \infty} F_{n+1}/F_n = \phi$
も分かる.
B
以下の関係式も成立する:
- $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}$
C
以下も成立する:
- $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$
が成立する.
具体例
自然界
動物
うさぎ🐇のつがい数
(参照リンク)
植物
ひまわりの種
松ぼっくりの鱗
階段の上り方
1段か2段で上るときの上り方の総数
敷き詰め方
2cm×20cmの長方形に, 1cm×2cmのブロックを敷き詰める組合わせ方
一山崩し
一山崩しの必勝法
$\pi$ の連分数展開
$$\pi = 3 + \frac{1^2}{6 + \frac{3^2}{6+\frac{5^2}{\cdots}}}$$
パスカルの三角形
いい感じの斜線を引き和を取ると現れる
株価
フィボナッチリトレースメント
(参照リンク)
類似の数列
フィボナッチ数列は $F_0=0$, $F_1=1$ かつ $n \geqq 2$ において, $F_{n} =F_{n-1} + F_{n-2}$ と定義される. この定義を発展させ, 類似の数列を定義する.
$0, \ 1, \ 1, \ 2, \ 3, \ 5, \ 8, \ 13, \ 21, \ 34, \ 55, \ \cdots$
トリボナッチ数列
$0 , \ 0, \ 1, \ 1, \ 2, \ 4, \ 7, \ 13, \ 24, \ 44, \ 81, \ 149, \ \cdots$
$F_{n+3} = F_{n+2} + F_{n+1} + F_n \ (n \geqq 3)$
$F_0=F_1 =0, \ F_2=1$
テトラナッチ数列
$0 , \ 0, \ 0, \ 1, \ 1, \ 2, \ 4, \ 8, \ 15, \ 29, \ 56, \ 108, \ 208, \ \cdots$
$F_{n+4} = F_{n+3} + F_{n+2} + F_{n+1} + F_n \ (n \geqq 4)$
$F_0=F_1 = F_2 = 0, \ F_3=1$
証明
三項間漸化式
$\phi = \frac{1+\sqrt{5}}{2}$ とします。
漸化式(定義)は次の2式に変形できます。
$$\left\{ \begin{array}{lll}
a_{n+2} - \phi a_{n+1} &=& \frac{1}{\phi}(a_{n+1} - \phi a_n) \\
a_{n+2} - \frac{1}{\phi} a_{n+1}&=& \phi(a_{n+1} - \frac{1}{\phi} a_n)
\end{array} \right. $$
数列 $\{ a_{n+1} - \phi a_n \}_n$ と $\{ a_{n+1} - \frac{1}{\phi} a_n \}_n$ が等比数列と分かるから,
$$\left\{ \begin{array}{lll}
a_{n+1} - \phi a_n &=& \frac{1}{\phi^n}\\
a_{n+1} - \frac{1}{\phi} a_n &=& \phi^n
\end{array} \right. $$
この2式を整理して, $$a_n = \frac{1}{\sqrt{5}} \left( \phi^n - \frac{1}{\phi^n} \right).$$