魔法少女になるための教養

【問題】

${ p_1 = 1,\, p_2 = 1,\, p_{n+2} = p_{n+1} + p_n \,(n \ge 1) }$ により定義される数列 ${ \{p_n\} }$ をフィボナッチ数列といい、その一般項は
　　 $p_n = \tfrac{1}{\sqrt{5}}\left\{\left(\tfrac{1+\sqrt{5}}{2}\right)^n-\left(\tfrac{1-\sqrt{5}}{2}\right)^n\right\}$
で与えられる。　この事実を踏まえて以下の問に答えよ。
各桁の数字が0か1である整数の列 ${ X_n\,(n=1,\,2,\,\cdots) }$ を次の規則により定める。
　(A) ${ X_1 = 1 }$
　(B) ${ X_n }$ のある桁の数字 ${ \alpha }$ が0ならば ${ \alpha }$ を1で置き換え、 ${ \alpha }$ が1ならば ${ \alpha }$ を10で置き換える。
${ X_n }$ の各行ごとにこのような置き換えを行って得られる自然数を ${ X_{n+1} }$ とする。　例えば、
　　 $X_1 = 1,\,X_2 = 10,\,X_3 = 101,\,X_4 = 10110,\, X_5 = 10110101,\,\cdots$
となる。
　(1) ${ X_n }$ の桁数 ${ a_n }$ を求めよ。
　(2) ${ X_n }$ の中に "01" という並びが現れる回数 ${ b_n }$ を求めよ。
（例） ${ b_1 = 0,\, b_2 = 0,\, b_3 = 1 }$

【解答】

(1) ${ X_n }$ の桁数 ${ a_n }$ を求めよ。

${ X_n }$ に含まれている1の個数を ${ x_n }$ 、0の個数を ${ y_n }$ とする。　(A) ${ X_1 = 1 }$ より

　　 $\begin{align*} x_1 &= 1 & \cdots(1) \\ y_1 & = 0 & \cdots(2) \end{align*}$

また、規則 (B) より以下の漸化式が成り立つ

　　 $\begin{align*} x_{n+1} &= x_n + y_n & \cdots(3) \\ y_{n+1} & = x_n & \cdots(4) \end{align*}$

☆ ${ x_n }$ の一般項を求める☆

(1), (2), (3) より

　　 $\begin{align*} x_2 &= x_1 + y_1 \\ &= 1 \end{align*}$

また、(3), (4) より

　　 $\begin{align*} x_{n+2} &= x_{n+1} + y_{n+1} \\ &= x_{n+1} + x_n \end{align*}$

よって

　　 $\begin{cases} x_1 = 1 \\ x_2 = 1 \\ x_{n+2} = x_{n+1} + x_n \end{cases}$

これはフィボナッチ数列 ${ p_n }$ の初項、第2項、漸化式に等しいので、 ${ x_n }$ はフィボナッチ数列に等しい。　つまり

　　 $x_n = p_n$

☆ ${ y_n }$ の一般項を求める☆

(4) より n≧2 のとき

　　 $\begin{align*} y_n &= x_{n-1} \\ & = p_{n-1} \end{align*}$

また (2) より

　　 $y_1 = 0$

よって*1

　　 $y_n = \begin{cases}1 & (n = 1) \\ p_{n-1} & (n \ge 2)\end{cases}$

☆ ${ a_n }$ を求める☆

${ a_n }$ は ${ x_n }$ , ${ y_n }$ を使って

　　 $a_n = x_n + y_n$

と書ける。　上記で求めた ${ x_n }$ , ${ y_n }$ の一般項の表式より、n≧2 のとき

　　 $\begin{align*} a_n &= x_n + y_n \\ &= p_n + p_{n-1} \\ &= p_{n+1} \end{align*}$

ここで

　　 $\begin{align*} a_1 &= x_1 + y_1 \\ &= 1 \\ p_2 &= 1 \end{align*}$

より、この表式は n=1 のときも成り立つ。　よって、 ${ a_n }$ は

　　 $a_n = p_{n+1}$

となる。

(2) ${ X_n }$ の中に "01" という並びが現れる回数 ${ b_n }$ を求めよ。

☆n≧2 の場合☆

規則 (B) より、この規則を適用して "01" となる数字の並びは "10", "11" のいずれか。　つまり1の後に0もしくは1が続いていれば、規則 (B) を適用して "01" が現れる。　したがって、 ${ b_n }$ は ${ X_{n-1} }$ の1の個数（ただし一番右の位の1は除く）に等しい。