九州大学 1996年 理系 第5問 解説

方針・初手

(1) は、語 $C_n$ を具体的に書き出し、規則性を予想して数学的帰納法で証明します。文字列としての結合を扱うため、文字列 $S$ を $m$ 回繰り返してできる語を $S^m$ と表記すると見通しが良くなります。 (2) は、$C_n$ に含まれる $0$ の個数 $a_n$、$1$ の個数 $b_n$ について、語の構成規則 $C_n = C_{n-2} C_{n-1} C_{n-2}$ から漸化式を立てて一般項を求めます。

解法1

(1)

語の結合を書き並べることで表し、文字列 $S$ を $m$ 回繰り返した語を $S^m$ と表す（$m=0$ のときは空の語とする）。 $C_1 = 1$ $C_2 = 10$ $C_3 = C_1 C_2 C_1 = 1101$ $C_4 = C_2 C_3 C_2 = 10110110$

ここで、任意の $0$ 以上の整数 $m$ に対して、以下の補題が成り立つ。

補題： $1(101)^m = (110)^m 1$ $10(110)^m = (101)^m 10$

（補題の証明） 「$1$ の後に $101$ を $m$ 回繰り返した語」は $1101101 \dots 101$ であり、これは「$110$ を $m$ 回繰り返した後に $1$ を付加した語」と一致する。よって前半は成り立つ。 同様に「$10$ の後に $110$ を $m$ 回繰り返した語」は $10110110 \dots 110$ であり、これは「$101$ を $m$ 回繰り返した後に $10$ を付加した語」と一致する。よって後半も成り立つ。

これを用いて、以下の命題 $P(n)$ が $n \geqq 3$ で成り立つことを数学的帰納法で示す。 「$0$ 以上の整数 $N_n$ が存在して、 $n$ が奇数のとき、$C_n = (110)^{N_n} 1 = 1 (101)^{N_n}$ $n$ が偶数のとき、$C_n = 10 (110)^{N_n} = (101)^{N_n} 10$ と表せる。」

(I) $n=3, 4$ のとき $C_3 = 1101 = 110 \cdot 1 = 1 \cdot 101$ より、$N_3 = 1$ として $P(3)$ は成立する。 $C_4 = 10110110 = 10 \cdot 110 \cdot 110 = 10(110)^2$ また $C_4 = 101 \cdot 101 \cdot 10 = (101)^2 10$ より、$N_4 = 2$ として $P(4)$ は成立する。

(II) $n=k, k+1$ ($k \geqq 3$) で $P(n)$ が成立すると仮定する。 (i) $k$ が奇数のとき 仮定より $C_k = (110)^{N_k} 1 = 1 (101)^{N_k}$、$C_{k+1} = 10 (110)^{N_{k+1}} = (101)^{N_{k+1}} 10$ である。 $n=k+2$ (奇数) について、

$$\begin{aligned} C_{k+2} &= C_k C_{k+1} C_k \\ &= \left\{ (110)^{N_k} 1 \right\} \left\{ 10 (110)^{N_{k+1}} \right\} \left\{ (110)^{N_k} 1 \right\} \\ &= (110)^{N_k} 110 (110)^{N_{k+1}} (110)^{N_k} 1 \\ &= (110)^{2N_k + N_{k+1} + 1} 1 \end{aligned}$$

また、別の表現を用いると、

$$\begin{aligned} C_{k+2} &= \left\{ 1 (101)^{N_k} \right\} \left\{ (101)^{N_{k+1}} 10 \right\} \left\{ 1 (101)^{N_k} \right\} \\ &= 1 (101)^{N_k} (101)^{N_{k+1}} 101 (101)^{N_k} \\ &= 1 (101)^{2N_k + N_{k+1} + 1} \end{aligned}$$

よって $N_{k+2} = 2N_k + N_{k+1} + 1$ とすれば $P(k+2)$ は成立する。

(ii) $k$ が偶数のとき 仮定より $C_k = 10 (110)^{N_k} = (101)^{N_k} 10$、$C_{k+1} = (110)^{N_{k+1}} 1 = 1 (101)^{N_{k+1}}$ である。 $n=k+2$ (偶数) について、

$$\begin{aligned} C_{k+2} &= C_k C_{k+1} C_k \\ &= \left\{ 10 (110)^{N_k} \right\} \left\{ (110)^{N_{k+1}} 1 \right\} \left\{ 10 (110)^{N_k} \right\} \end{aligned}$$

ここで $(110)^{N_{k+1}} 1 \cdot 10 = (110)^{N_{k+1}} 110$ であるから、

$$\begin{aligned} C_{k+2} &= 10 (110)^{N_k} (110)^{N_{k+1}} 110 (110)^{N_k} \\ &= 10 (110)^{2N_k + N_{k+1} + 1} \end{aligned}$$

また、別の表現を用いると、

$$\begin{aligned} C_{k+2} &= \left\{ (101)^{N_k} 10 \right\} \left\{ 1 (101)^{N_{k+1}} \right\} \left\{ (101)^{N_k} 10 \right\} \end{aligned}$$

ここで $10 \cdot 1 (101)^{N_{k+1}} = 101 (101)^{N_{k+1}}$ であるから、

$$\begin{aligned} C_{k+2} &= (101)^{N_k} 101 (101)^{N_{k+1}} (101)^{N_k} 10 \\ &= (101)^{2N_k + N_{k+1} + 1} 10 \end{aligned}$$

よって $N_{k+2} = 2N_k + N_{k+1} + 1$ とすれば $P(k+2)$ は成立する。

(I), (II) より、すべての $n \geqq 3$ について $P(n)$ が成り立つ。 したがって、 $n$ が奇数のとき、$C_n$ の最後の $1$ 文字を取り去ると語 $110$ が循環し、最初の $1$ 文字を取り去ると語 $101$ が循環する。 $n$ が偶数のとき、$C_n$ の最初の $2$ 文字を取り去ると語 $110$ が循環し、最後の $2$ 文字を取り去ると語 $101$ が循環する。 いずれの場合も、最初または最後の数字を $1$ 個か $2$ 個取り去ると、残りは同じ語が循環して現れることが示された。

(2)

$C_n = C_{n-2} C_{n-1} C_{n-2} \;\; (n \geqq 3)$ より、語 $C_n$ に含まれる $0$ の個数 $a_n$ と $1$ の個数 $b_n$ について以下の漸化式が成り立つ。

$$a_n = 2a_{n-2} + a_{n-1}$$

$$b_n = 2b_{n-2} + b_{n-1}$$

$C_1 = 1, C_2 = 10$ であるから、初期条件は $a_1 = 0, a_2 = 1$ および $b_1 = 1, b_2 = 1$ である。 $a_n - a_{n-1} - 2a_{n-2} = 0$ は、以下のように $2$ 通りに変形できる。

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

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

それぞれ等比数列となるので、

$$a_n - 2a_{n-1} = (a_2 - 2a_1)(-1)^{n-2} = (-1)^n \quad \dots \text{①}$$

$$a_n + a_{n-1} = (a_2 + a_1) \cdot 2^{n-2} = 2^{n-2} \quad \dots \text{②}$$

② $-$ ① より、

$$3a_{n-1} = 2^{n-2} - (-1)^n$$

$n$ を $n+1$ に置き換えて、

$$a_n = \frac{1}{3} \cdot 2^{n-1} - \frac{1}{3}(-1)^{n+1} = \frac{1}{3} \cdot 2^{n-1} + \frac{1}{3}(-1)^n$$

同様に、$b_n$ についても、

$$b_n - 2b_{n-1} = -(b_{n-1} - 2b_{n-2})$$

$$b_n + b_{n-1} = 2(b_{n-1} + b_{n-2})$$

初期条件を代入して、

$$b_n - 2b_{n-1} = (b_2 - 2b_1)(-1)^{n-2} = -(-1)^n \quad \dots \text{③}$$

$$b_n + b_{n-1} = (b_2 + b_1) \cdot 2^{n-2} = 2 \cdot 2^{n-2} = 2^{n-1} \quad \dots \text{④}$$

④ $-$ ③ より、

$$3b_{n-1} = 2^{n-1} + (-1)^n$$

$n$ を $n+1$ に置き換えて、

$$b_n = \frac{1}{3} \cdot 2^n + \frac{1}{3}(-1)^{n+1} = \frac{1}{3} \cdot 2^n - \frac{1}{3}(-1)^n$$

したがって、求める極限は、

$$\lim_{n \to \infty} \frac{a_n}{b_n} = \lim_{n \to \infty} \frac{\frac{1}{3} \cdot 2^{n-1} + \frac{1}{3}(-1)^n}{\frac{1}{3} \cdot 2^n - \frac{1}{3}(-1)^n}$$

分母分子に $3$ を掛け、$2^n$ で割ると、

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

$n \to \infty$ のとき $\left(-\frac{1}{2}\right)^n \to 0$ であるから、

$$\lim_{n \to \infty} \frac{a_n}{b_n} = \frac{1}{2}$$

解説

(1) は文字列の結合に関する問題です。一般に文字列の結合は交換法則が成り立たないため、結合の順序を厳密に保ちながら変形する必要があります。「$C_n$ が同じ語の循環になる」という曖昧な表現を、「$(110)^m 1$ などの形で書ける」という数式的な命題に翻訳して帰納法を回すのが定石です。

(2) は構成規則から文字数に関する隣接3項間漸化式を導出する典型的な問題です。特性方程式 $\lambda^2 - \lambda - 2 = 0$ を解いて2つの等比数列を作り、差分をとって一般項を求める手順は頻出ですので、確実に計算できるようにしておきましょう。

答え

(1) 略（解答参照） (2) $\displaystyle\frac{1}{2}$