2 フィボナッチ数列

まず、フィボナッチ数列とうさぎの話を紹介する。 元々の問題は以下のようである。

うさぎのつがいが 1 組あると、それが毎月 2 匹のうさぎを産み、 その子がまたつがいとなり、 2 ヶ月後からは親と同じように毎月 1 つがいのうさぎを産むようになる。 $n$ ヶ月後には何つがいのうさぎがいることになるか。

この問題の設定は、 生物学的には不自然なところもかなりあるのであろうが、 繁殖力の強い動物の増え方の近似的な様子を見るには、 それなりに役に立つのだろう。

この問題を、産まれたばかりの 1 つがいのうさぎから考えることとし、 $n$ ヶ月後に産まれたばかりのつがいの数を $\alpha_n$、 生後 1 ヶ月経ったつがいの数を $\beta_n$、 生後 2 ヶ月以降の親つがいの数を $\gamma_n$ とすると、 開始時は

$$\alpha_0 = 1, \hspace{1zw}\beta_0 = 0, \hspace{1zw}\gamma_0 = 0$$ (2)

であり、1 ヶ月後には

$$\alpha_1 = 0, \hspace{1zw}\beta_1 = 1, \hspace{1zw}\gamma_1 = 0$$ (3)

となり、2 ヶ月後にはその最初のつがいは親つがいとなり、子を産むので、

$$\alpha_2 = 1, \hspace{1zw}\beta_2 = 0, \hspace{1zw}\gamma_2 = 1$$ (4)

となる。以下、親つがいは毎月子を産むので、

$$\begin{array}{lll} \alpha_3 = 1, & \beta_3 = 1, & \gamma_3 ... ...2,\\ \alpha_5 = 3, & \beta_5 = 2, & \gamma_5 = 3, \end{array}$$

のように推移していく。 つがいの総数を $N_n = \alpha_n+\beta_n+\gamma_n$ とすると、

$$N_0 = 1, \hspace{1zw}N_1 = 1, \hspace{1zw}N_2 = 2, \hspace{1zw}N_3 = 3, \hspace{1zw}N_4 = 5, \hspace{1zw}N_5 = 8,$$

のように確かにフィボナッチ数列となりそうだが ($N_n=F_{n+1}$)、 実際に $N_n$ に (1) のような漸化式が成り立つことを確認する。

上の定義と考察により、 $\alpha_n$, $\beta_n$, $\gamma_n$ には次の関係が成り立つことがわかる。

$$\gamma_n = \gamma_{n-1} + \beta_{n-1}\hspace{1zw}(n\geq 1),$$ (5)

$$\beta_n = \alpha_{n-1} \hspace{1zw}(n\geq 1),$$ (6)

$$\alpha_n = \gamma_n \hspace{1zw}(n\geq 1)$$ (7)

(5) は親つがいの数 $\gamma_n$ で、 それは 1 ヶ月前に既に親だったつがいの数 $\gamma_{n-1}$ と、 1 ヶ月前に生後 1 ヶ月だったつがいの数 $\beta_{n-1}$ の和に等しい。

(6) は生後 1 ヶ月のつがいの数 $\beta_n$ で、 それは 1 ヶ月前には産まれたばかりのつがいの数 $\alpha_{n-1}$ に等しい。

(7) は産まれたばかりのつがいの数 $\alpha_n$ で、 それは現在の親つがいの数 $\gamma_n$ に等しい。

ここから、$\gamma_n$ の漸化式を作ってみる。 どの $n$ に対して成り立つかも注意しながら見てみると、 (5), (6), (7) より、

$$\begin{eqnarray*}\gamma_n &=& \gamma_{n-1} + \beta_{n-1}\hspace{1zw}(n\geq 1) ... ...n\geq 2) \\ &=& \gamma_{n-1} + \gamma_{n-2}\hspace{1zw}(n\geq 3)\end{eqnarray*}$$

となるので、$\gamma_n$ は $n\geq 3$ ではフィボナッチ数列 (1) の漸化式を満たすことがわかるが、 $(\gamma_0,\gamma_1,\gamma_2)=(0,0,1)$ なので、$n=2$ では その漸化式は満たさず、 $\gamma_2 = \gamma_1 + \gamma_0 + 1$ となっている。

同様に、$\alpha_n$ は、

$$\begin{eqnarray*}\alpha_n &=& \gamma_n\hspace{1zw}(n\geq 1) \\ &=& \gamma_{n-... ...n\geq 3) \\ &=& \alpha_{n-1} + \alpha_{n-2}\hspace{1zw}(n\geq 3)\end{eqnarray*}$$

より、$\alpha_n$ も $n\geq 3$ で同じ漸化式を満たすが、 $(\alpha_0,\alpha_1,\alpha_2)=(1,0,1)$ なので、 この漸化式は $n=2$ でも成り立つ。 $\beta_n$ は、

$$\begin{eqnarray*}\beta_n &=& \alpha_{n-1}\hspace{1zw}(n\geq 1) \\ &=& \alpha_... ...}(n\geq 3) \\ &=& \beta_{n-1} + \beta_{n-2}\hspace{1zw}(n\geq 3)\end{eqnarray*}$$

となり、やはり $n\geq 3$ で (1) の漸化式を満たし、 $(\beta_0,\beta_1,\beta_2)=(0,1,0)$ より、$n=2$ では $\beta_2=\beta_1+\beta_0-1$ となっている。 結局、$n\geq 2$ で以下が成り立つ。

$$\gamma_n = \gamma_{n-1}+\gamma_{n-2} + \delta_{n,2}, \hspa... ...\delta_{n,2}, \hspace{1zw}\alpha_n = \alpha_{n-1}+\alpha_{n-2}$$ (8)

ここで $\delta_{i,j}=0$ ($i\neq j$), $\delta_{i,i}=1$ とする。 よって、これらの和により

$$N_n = N_{n-1}+N_{n-2}\hspace{1zw}(n\geq 2)$$ (9)

となることがわかる。

さらに $N_0=N_1=1$ なので、よって $N_n=F_{n+1}$ ($n\geq 0$) となる。 なお、同様に、

$$\alpha_n = F_{n-1}\hspace{1zw}(n\geq 2), \hspace{1zw}\beta... ...(n\geq 3), \hspace{1zw}\gamma_n = F_{n-1}\hspace{1zw}(n\geq 2)$$ (10)

もいえる。 すなわち、$\alpha_n$, $\beta_n$, $\gamma_n$, $N_n$ は いずれもフィボナッチ数列の漸化式を満たし、 実際に部分的にはフィボナッチ数列に一致する。

さて、本節の最後にフィボナッチ数列の一般項を求めておく。 [1] で示したように、 定数係数線形の漸化式は、特性方程式を解けばその一般項が求まる。 フィボナッチ数列 $\{F_n\}_n$ の特性方程式は、

$$\lambda^2 = \lambda + 1$$ (11)

であり、この 2 次方程式の解は

$$\lambda_1 = \frac{1-\sqrt{5}}{2}, \hspace{1zw} \lambda_2 = \frac{1+\sqrt{5}}{2}$$

であるから、 $F_n = c_1\lambda_1^n + c_2\lambda_2^n$ となるが、 ここに $n=1$, $n=2$ を代入して (1) を用いると、

$$c_1\lambda_1+c_2\lambda_2 = 1, \hspace{1zw} c_1\lambda_1^2+c_2\lambda_2^2 = 1$$

となるから、

$$c_1 = \frac{\lambda_2-1}{\lambda_1(\lambda_2-\lambda_1)} =... ... = \frac{\lambda_2}{\sqrt{5}\,\lambda_2} = \frac{1}{\sqrt{5}}$$

となるので、よって、

$$F_n = \frac{1}{\sqrt{5}}(-\lambda_1^n + \lambda_2^n) = \fr... ...t{5}}{2}\right)^n -\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}$$ (12)

が得られる。 なお、高校では [1] に書いたような理論を 教えるわけではないので、 3 項漸化式などをこのようには解かない。