東北大学 1990年 理系 第6問 解説

方針・初手

長さ $n$ の列から長さ $n+1$ の列を作るとき、末尾2文字の状態だけを見れば十分である。

末尾2文字が同じか異なるかで分類してあるので、1文字付け足したときにどちらへ遷移するかを整理する。すると $(a_n,b_n)$ の漸化式が得られ、さらに $a_n+rb_n$ という一次結合が等比数列になる条件も直接調べられる。

解法1

まず、長さ $2$ の列は

$$ ++,\ --,\ +-,\ -+ $$

の4個であり、いずれも条件を満たすから

$$ a_2=2,\qquad b_2=2 $$

である。

(1) $a_{n+1},,b_{n+1}$ を $a_n,,b_n$ で表す。

長さ $n$ の列で、末尾2文字が同じものを1つとる。たとえば末尾が $++$ なら、さらに $+$ を付けると $+++$ となって同じ記号が3個連続してしまうので不適である。付け足せるのは反対の記号だけであり、そのとき末尾2文字は異なる。

同様に、末尾2文字が異なるものを1つとる。たとえば末尾が $+-$ なら、最後の $-$ と同じ記号を付ければ末尾2文字は同じになり、反対の記号を付ければ末尾2文字は異なる。いずれも同じ記号3個連続にはならない。

したがって、

• $a_n$ に数えられる列は、長さ $n+1$ では $b_{n+1}$ にのみ1個ずつ移る。
• $b_n$ に数えられる列は、長さ $n+1$ では $a_{n+1},,b_{n+1}$ に1個ずつ移る。

よって

$$ a_{n+1}=b_n,\qquad b_{n+1}=a_n+b_n $$

である。

(2) ${a_n+rb_n}$ が公比 $r$ の等比数列となるような $r$ を求める。

$$ x_n=a_n+rb_n $$

とおく。

これが公比 $r$ の等比数列であるとは、

$$ x_{n+1}=rx_n $$

が成り立つことと同値である。

(1) の関係式を用いると

$$ x_{n+1}=a_{n+1}+rb_{n+1} =b_n+r(a_n+b_n) =ra_n+(r+1)b_n $$

である。一方、

$$ rx_n=r(a_n+rb_n)=ra_n+r^2b_n $$

であるから、両者が一致するためには

$$ (r+1)b_n=r^2b_n $$

が必要である。

ここで $b_n>0$ であるから、

$$ r^2-r-1=0 $$

を得る。よって

$$ r=\frac{1+\sqrt5}{2},\qquad r=\frac{1-\sqrt5}{2} $$

である。

(3) 長さ $n$ のこのような列の個数 $a_n+b_n$ を、(2) で求めた $r$ の値を使って表す。

$$ \alpha=\frac{1+\sqrt5}{2},\qquad \beta=\frac{1-\sqrt5}{2} $$

とおく。

(2) より、${a_n+\alpha b_n}$ は公比 $\alpha$ の等比数列、${a_n+\beta b_n}$ は公比 $\beta$ の等比数列である。

初期値 $a_2=b_2=2$ を用いると、

$$ a_2+\alpha b_2=2+2\alpha=2(1+\alpha)=2\alpha^2 $$

であるから、

$$ a_n+\alpha b_n=2\alpha^n $$

同様に、

$$ a_n+\beta b_n=2\beta^n $$

である。

この2式を引くと

$$ (\alpha-\beta)b_n=2(\alpha^n-\beta^n) $$

となる。$\alpha-\beta=\sqrt5$ だから、

$$ b_n=\frac{2}{\sqrt5}\left(\alpha^n-\beta^n\right) $$

を得る。

さらに (1) より

$$ a_n+b_n=b_{n+1} $$

であるから、

$$ a_n+b_n =\frac{2}{\sqrt5}\left(\alpha^{n+1}-\beta^{n+1}\right) $$

すなわち

$$ a_n+b_n =\frac{2}{\sqrt5} \left\{ \left(\frac{1+\sqrt5}{2}\right)^{n+1} -\left(\frac{1-\sqrt5}{2}\right)^{n+1} \right\} $$

である。

解説

この問題の本質は、列全体を直接数えるのではなく、末尾2文字の状態だけで分類することである。条件が「同じ記号が3個以上連続しない」なので、1文字追加したときに必要な情報は末尾2文字だけで足りる。

また、$a_n+rb_n$ という一次結合を考えると、漸化式

$$ \begin{pmatrix} a_{n+1}\ b_{n+1} \end{pmatrix} ============= \begin{pmatrix} 0&1\ 1&1 \end{pmatrix} \begin{pmatrix} a_n\ b_n \end{pmatrix} $$

の固有値に対応する形になっている。(2) の $r^2-r-1=0$ はその固有方程式に一致しており、最終的にフィボナッチ型の式が現れる。

答え

$$ a_{n+1}=b_n,\qquad b_{n+1}=a_n+b_n $$

$$ r=\frac{1+\sqrt5}{2},\qquad r=\frac{1-\sqrt5}{2} $$

$$ a_n+b_n =\frac{2}{\sqrt5} \left{ \left(\frac{1+\sqrt5}{2}\right)^{n+1} ------------------------------------- \left(\frac{1-\sqrt5}{2}\right)^{n+1} \right} $$