AとBの2種類の文字を用いて、$n$個並べた文字列全体の集合を$X_n$とする。ただし、Bが連続しないようにする。$X_n$の2つの部分集合を、$S_n = \{x | x \in X_n \text{ かつ } x \text{ の最後の文字がA}\}$、$T_n = \{x | x \in X_n \text{ かつ } x \text{ の最後の文字がB}\}$とする。$S_n$の要素の個数を$a_n$、$T_n$の要素の個数を$b_n$とおく。 (i) $a_3, b_3, a_4, b_4$ を求めよ。 (ii) $a_{n+1}, b_{n+1}$ をそれぞれ$a_n$ と $b_n$ を用いて表せ。 (iii) $a_n \ge 100$ と $b_n \ge 100$ をともに満たす最小の $n$ を求めよ。 (iv) 自然数 $a, b$ と $c = a + b$ に対して、$L = \{d | d \text{ は } a, b \text{ の公約数}\}$、$R = \{d | d \text{ は } a, c \text{ の公約数}\}$ とする。$L \subset R$ と $L \supset R$ がともに成り立つこと（つまり $L = R$）を示せ。また、すべての自然数 $m$ に対して、$a_m$ と $b_m$ は互いに素であることを数学的帰納法により示せ。 (v) $r_n = \frac{a_n}{a_n + b_n}$ とする。ある関数 $f(x)$ により等式 $r_{m+1} = f(r_m)$ がすべての自然数 $m$ について成立する。$f(x)$ をひとつ求めよ。また、極限値 $\lim_{m \to \infty} r_m$ を求めよ。

1. 問題の内容

AとBの2種類の文字を用いて、$n$個並べた文字列全体の集合を$X_n$とする。ただし、Bが連続しないようにする。$X_n$の2つの部分集合を、$S_n = \{x | x \in X_n \text{ かつ } x \text{ の最後の文字がA}\}$、$T_n = \{x | x \in X_n \text{ かつ } x \text{ の最後の文字がB}\}$とする。$S_n$の要素の個数を$a_n$、$T_n$の要素の個数を$b_n$とおく。

(i) $a_3, b_3, a_4, b_4$ を求めよ。

(ii) $a_{n+1}, b_{n+1}$ をそれぞれ$a_n$ と $b_n$ を用いて表せ。

(iii) $a_n \ge 100$ と $b_n \ge 100$ をともに満たす最小の $n$ を求めよ。

(iv) 自然数 $a, b$ と $c = a + b$ に対して、$L = \{d | d \text{ は } a, b \text{ の公約数}\}$、$R = \{d | d \text{ は } a, c \text{ の公約数}\}$ とする。$L \subset R$ と $L \supset R$ がともに成り立つこと（つまり $L = R$）を示せ。また、すべての自然数 $m$ に対して、$a_m$ と $b_m$ は互いに素であることを数学的帰納法により示せ。

(v) $r_n = \frac{a_n}{a_n + b_n}$ とする。ある関数 $f(x)$ により等式 $r_{m+1} = f(r_m)$ がすべての自然数 $m$ について成立する。$f(x)$ をひとつ求めよ。また、極限値 $\lim_{m \to \infty} r_m$ を求めよ。

2. 解き方の手順

(i) $n=3$ のとき、$X_3$ を考える。Bが連続しないように並べる。

最後の文字がAであるものは、AA, ABA, BAA, BAB. よって $a_3 = 3$.

最後の文字がBであるものは、AAB, BAB. よって $b_3 = 2$.

$n=4$ のとき、$X_4$ を考える。

最後の文字がAであるものは、AAAA, AABA, ABAA, ABAB, BAAA, BAAB, BABA. よって $a_4 = 5$.

最後の文字がBであるものは、AAAB, ABAB, BAAAB, BABAB, ABAB. よって $b_4 = 3$.

(ii) $a_{n+1}$ は、長さ$n$の文字列で最後にAがつくもの($a_n$個)にAをつけたものと、長さ$n$の文字列で最後にBがつくもの($b_n$個)にAをつけたものからなる。よって、$a_{n+1} = a_n + b_n$.

$b_{n+1}$ は、長さ$n$の文字列で最後にAがつくもの($a_n$個)にBをつけたものからなる。よって、$b_{n+1} = a_n$.

(iii) $a_{n+1} = a_n + b_n = a_n + a_{n-1}$ という漸化式が成り立つ。また、$a_1 = 1, a_2 = 2$.

$a_3 = 3, a_4 = 5, a_5 = 8, a_6 = 13, a_7 = 21, a_8 = 34, a_9 = 55, a_{10} = 89, a_{11} = 144$.

$b_{n+1} = a_n$. よって、$b_2 = 1, b_3 = 2, b_4 = 3, b_5 = 5, b_6 = 8, b_7 = 13, b_8 = 21, b_9 = 34, b_{10} = 55, b_{11} = 89, b_{12} = 144$.

$a_n \ge 100$ と $b_n \ge 100$ を満たす最小の $n$ は $n = 11$ ($a_{11} = 144 \ge 100$ かつ $b_{12} = 144 \ge 100$)。ただし、$n=11$のとき$b_{11}=89$であるから、$a_{12} = a_{11} + b_{11} = 144+89 = 233$. $n=12$のとき$b_{12} = a_{11} = 144$. よって$n=11$では不適。

$n = 12$のとき$a_{12}=233 > 100$かつ$b_{12} = 144 > 100$なので、$n = 12$

(iv) $L = \{d | d \text{ は } a, b \text{ の公約数}\}$、$R = \{d | d \text{ は } a, c \text{ の公約数}\}$ とする。$c = a + b$ である。

$L \subset R$ を示す。$d \in L$ とする。すると、$d$ は $a$ と $b$ の公約数である。したがって、$a = d k_1, b = d k_2$ （$k_1, k_2$ は整数）と表せる。このとき、$c = a + b = d k_1 + d k_2 = d (k_1 + k_2)$ であるから、$d$ は $c$ の約数でもある。したがって、$d$ は $a$ と $c$ の公約数であり、$d \in R$ である。ゆえに、$L \subset R$.

$L \supset R$ を示す。$d \in R$ とする。すると、$d$ は $a$ と $c$ の公約数である。したがって、$a = d k_1, c = d k_3$ （$k_1, k_3$ は整数）と表せる。このとき、$b = c - a = d k_3 - d k_1 = d (k_3 - k_1)$ であるから、$d$ は $b$ の約数でもある。したがって、$d$ は $a$ と $b$ の公約数であり、$d \in L$ である。ゆえに、$L \supset R$.

以上より、$L = R$ である。

$a_m$ と $b_m$ は互いに素であることを数学的帰納法で示す。

(i) $m=1$ のとき、$a_1 = 1, b_1 = 1$ であり、これらは互いに素である。

(ii) $m=k$ のとき、$a_k$ と $b_k$ が互いに素であると仮定する。

$m=k+1$ のとき、$a_{k+1} = a_k + b_k$ と $b_{k+1} = a_k$ について考える。

$a_{k+1}$ と $b_{k+1}$ の公約数を $d$ とすると、$a_{k+1} = d n_1, b_{k+1} = d n_2$ （$n_1, n_2$ は整数）と表せる。

このとき、$a_k = b_{k+1} = d n_2$ であり、$b_k = a_{k+1} - a_k = d n_1 - d n_2 = d (n_1 - n_2)$ である。

したがって、$d$ は $a_k$ と $b_k$ の公約数である。仮定より、$a_k$ と $b_k$ は互いに素であるから、$d = 1$ でなければならない。

したがって、$a_{k+1}$ と $b_{k+1}$ は互いに素である。

(i)(ii)より、すべての自然数 $m$ に対して、$a_m$ と $b_m$ は互いに素である。

(v) $r_n = \frac{a_n}{a_n + b_n}$ とする。$r_{m+1} = f(r_m)$ を求める。

$r_{m+1} = \frac{a_{m+1}}{a_{m+1} + b_{m+1}} = \frac{a_m + b_m}{a_m + b_m + a_m} = \frac{a_m + b_m}{2 a_m + b_m} = \frac{1}{\frac{2a_m + b_m}{a_m + b_m}} = \frac{1}{1 + \frac{a_m}{a_m + b_m}} = \frac{1}{1 + r_m}$.

よって、$f(x) = \frac{1}{1+x}$.

$\lim_{m \to \infty} r_m = L$ とすると、$L = \frac{1}{1+L}$ が成り立つ。

$L^2 + L - 1 = 0$. $L = \frac{-1 \pm \sqrt{1^2 - 4 \cdot 1 \cdot (-1)}}{2} = \frac{-1 \pm \sqrt{5}}{2}$.

$r_n = \frac{a_n}{a_n + b_n} > 0$ であるから、$L = \frac{-1 + \sqrt{5}}{2}$ である。

3. 最終的な答え

(i) $a_3 = 3, b_3 = 2, a_4 = 5, b_4 = 3$

(ii) $a_{n+1} = a_n + b_n, b_{n+1} = a_n$

(iii) $n = 12$

(iv) 証明は上記参照

(v) $f(x) = \frac{1}{1+x}, \lim_{m \to \infty} r_m = \frac{-1 + \sqrt{5}}{2}$