• まとめ
  • 具体例

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

前の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. フィボナッチ数列の多項間の性質

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

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

  1. $p,q \in \mathbf{N}$ の最大公約数が $r$ ならば, $F_p$ と $F_q$ の最大公約数は $F_r$ である
  2. 連続する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

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

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

C

以下も成立する:

  1. $F_m$ が偶数 $\Leftrightarrow$ $m$ が $3$ の倍数
  2. $F_m$ が $5$ の倍数 $\Leftrightarrow$ $m$ が $5$ の倍数
  3. $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).$$