0と1からなる長さ $n$ ($n \ge 1$) の数列のうち、0が連続する並びを含まない数列の集合を $P_n$ 、その要素の個数を $a_n$ とする。 (1) $P_2$, $P_3$, $a_2$, $a_3$ をそれぞれ求める。 (2) $n \ge 1$ のとき、$a_{n+2}$ を $a_{n+1}$, $a_n$ を用いて表す。 (3) 2次方程式 $x^2 - x - 1 = 0$ の2つの解を $\alpha$, $\beta$ ($\alpha > \beta$) とするとき、数列 $\{a_n\}$ の一般項が $a_n = \frac{1}{\sqrt{5}}(\alpha^{n+2} - \beta^{n+2})$ で与えられることを示す。

1. 問題の内容

0と1からなる長さ $n$ ($n \ge 1$) の数列のうち、0が連続する並びを含まない数列の集合を $P_n$ 、その要素の個数を $a_n$ とする。

(1) $P_2$, $P_3$, $a_2$, $a_3$ をそれぞれ求める。

(2) $n \ge 1$ のとき、$a_{n+2}$ を $a_{n+1}$, $a_n$ を用いて表す。

(3) 2次方程式 $x^2 - x - 1 = 0$ の2つの解を $\alpha$, $\beta$ ($\alpha > \beta$) とするとき、数列 $\{a_n\}$ の一般項が $a_n = \frac{1}{\sqrt{5}}(\alpha^{n+2} - \beta^{n+2})$ で与えられることを示す。

2. 解き方の手順

(1) $P_2$, $P_3$, $a_2$, $a_3$ を求める。

$P_2$ は長さ2で、0が連続しない数列の集合であるから、$P_2 = \{01, 10, 11\}$。よって、$a_2 = 3$。

$P_3$ は長さ3で、0が連続しない数列の集合であるから、$P_3 = \{010, 011, 101, 110, 111\}$。よって、$a_3 = 5$。

(2) $a_{n+2}$ を $a_{n+1}$, $a_n$ を用いて表す。

長さ $n+2$ の数列で0が連続しないものを考える。

先頭が1の場合、残りの $n+1$ 個は0が連続しない数列であれば良いので、$a_{n+1}$ 通り。

先頭が0の場合、次の数は必ず1なので、残りの $n$ 個は0が連続しない数列であれば良いので、$a_n$ 通り。

よって、$a_{n+2} = a_{n+1} + a_n$。

(3) 数列 $\{a_n\}$ の一般項が $a_n = \frac{1}{\sqrt{5}}(\alpha^{n+2} - \beta^{n+2})$ で与えられることを示す。

2次方程式 $x^2 - x - 1 = 0$ の解は、解の公式より

$x = \frac{1 \pm \sqrt{1 - 4(-1)}}{2} = \frac{1 \pm \sqrt{5}}{2}$

$\alpha = \frac{1 + \sqrt{5}}{2}$, $\beta = \frac{1 - \sqrt{5}}{2}$ とする。

$a_{n+2} = a_{n+1} + a_n$ は、$a_{n+2} - \alpha a_{n+1} = \beta (a_{n+1} - \alpha a_n)$ と変形できる。

$a_1 = 2$, $a_2 = 3$ である。

$a_n = \frac{1}{\sqrt{5}}(\alpha^{n+2} - \beta^{n+2})$ を数学的帰納法で示す。

(i) $n=1$ のとき

$\frac{1}{\sqrt{5}}(\alpha^3 - \beta^3) = \frac{1}{\sqrt{5}} ((\frac{1+\sqrt{5}}{2})^3 - (\frac{1-\sqrt{5}}{2})^3) = \frac{1}{\sqrt{5}} (\frac{1+3\sqrt{5}+15+5\sqrt{5}}{8} - \frac{1-3\sqrt{5}+15-5\sqrt{5}}{8}) = \frac{1}{\sqrt{5}} (\frac{16+8\sqrt{5} - (16-8\sqrt{5})}{8}) = \frac{1}{\sqrt{5}} \frac{16\sqrt{5}}{8} = 2 = a_1$

$n=2$ のとき

$\frac{1}{\sqrt{5}}(\alpha^4 - \beta^4) = \frac{1}{\sqrt{5}} ((\frac{1+\sqrt{5}}{2})^4 - (\frac{1-\sqrt{5}}{2})^4) = \frac{1}{\sqrt{5}} (\frac{(6+2\sqrt{5})^2 - (6-2\sqrt{5})^2}{16}) = \frac{1}{\sqrt{5}} (\frac{36+24\sqrt{5}+20 - (36-24\sqrt{5}+20)}{16}) = \frac{1}{\sqrt{5}} \frac{48\sqrt{5}}{16} = 3 = a_2$

(ii) $n=k, k+1$ で成り立つと仮定する。すなわち、

$a_k = \frac{1}{\sqrt{5}}(\alpha^{k+2} - \beta^{k+2})$

$a_{k+1} = \frac{1}{\sqrt{5}}(\alpha^{k+3} - \beta^{k+3})$

このとき、$a_{k+2} = a_{k+1} + a_k = \frac{1}{\sqrt{5}}(\alpha^{k+3} - \beta^{k+3}) + \frac{1}{\sqrt{5}}(\alpha^{k+2} - \beta^{k+2}) = \frac{1}{\sqrt{5}}(\alpha^{k+2}(\alpha+1) - \beta^{k+2}(\beta+1))$

$\alpha, \beta$ は $x^2 = x+1$ を満たすので、$\alpha+1 = \alpha^2$, $\beta+1 = \beta^2$

$a_{k+2} = \frac{1}{\sqrt{5}}(\alpha^{k+2}\alpha^2 - \beta^{k+2}\beta^2) = \frac{1}{\sqrt{5}}(\alpha^{k+4} - \beta^{k+4})$

よって、$n=k+2$ のときも成り立つ。

したがって、すべての $n$ について、$a_n = \frac{1}{\sqrt{5}}(\alpha^{n+2} - \beta^{n+2})$ が成り立つ。

3. 最終的な答え

(1) $P_2 = \{01, 10, 11\}$, $P_3 = \{010, 011, 101, 110, 111\}$, $a_2 = 3$, $a_3 = 5$

(2) $a_{n+2} = a_{n+1} + a_n$

(3) $a_n = \frac{1}{\sqrt{5}}(\alpha^{n+2} - \beta^{n+2})$