正の整数 $n$ に対して、A, B, C の 3 種類の文字から重複を許して $n$ 個の文字を 1 列に並べるとき、A と B が隣り合わない並べ方の総数を $f_n$ とする。 (1) A と B が隣り合わない並べ方のうち、$n$ 番目が A または B であるものを $g_n$ 通り、$n$ 番目が C であるものを $h_n$ 通りとする。このとき、$g_{n+1}$ と $h_{n+1}$ を $g_n$ と $h_n$ を用いて表せ。 (2) 数列 $\{f_n\}$ に対して、$f_{n+2}$ を $f_{n+1}$ と $f_n$ を用いて表せ。 (3) $a_n = \frac{f_{n+1}}{f_n}$ により定まる数列 $\{a_n\}$ について、$a_n$ と $a_{n+1}$ の大小関係を調べよ。

1. 問題の内容

正の整数 $n$ に対して、A, B, C の 3 種類の文字から重複を許して $n$ 個の文字を 1 列に並べるとき、A と B が隣り合わない並べ方の総数を $f_n$ とする。

(1) A と B が隣り合わない並べ方のうち、$n$ 番目が A または B であるものを $g_n$ 通り、$n$ 番目が C であるものを $h_n$ 通りとする。このとき、$g_{n+1}$ と $h_{n+1}$ を $g_n$ と $h_n$ を用いて表せ。

(2) 数列 $\{f_n\}$ に対して、$f_{n+2}$ を $f_{n+1}$ と $f_n$ を用いて表せ。

(3) $a_n = \frac{f_{n+1}}{f_n}$ により定まる数列 $\{a_n\}$ について、$a_n$ と $a_{n+1}$ の大小関係を調べよ。

2. 解き方の手順

(1) $g_{n+1}$ と $h_{n+1}$ を $g_n$ と $h_n$ で表す。

$n+1$ 番目が A または B である並べ方は、$n$ 番目が A または B である $g_n$ 通りのそれぞれに対して、末尾に A または C を付加できる。また、$n$ 番目が C である $h_n$ 通りのそれぞれに対して、末尾に A または B を付加できる。したがって、

$$g_{n+1} = g_n + 2h_n$$

$n+1$ 番目が C である並べ方は、$n$ 番目が A または B である $g_n$ 通りのそれぞれに対して、末尾に C を付加できる。また、$n$ 番目が C である $h_n$ 通りのそれぞれに対して、末尾に C を付加できる。したがって、

$$h_{n+1} = g_n + h_n$$

(2) $f_{n+2}$ を $f_{n+1}$ と $f_n$ で表す。

$f_n = g_n + h_n$ であるから、

$$g_n = f_n - h_n$$

(1) より、

$$g_{n+1} = g_n + 2h_n$$

$$h_{n+1} = g_n + h_n$$

したがって、

$$f_{n+1} = g_{n+1} + h_{n+1} = (g_n + 2h_n) + (g_n + h_n) = 2g_n + 3h_n$$

$$f_{n+2} = g_{n+2} + h_{n+2} = (g_{n+1} + 2h_{n+1}) + (g_{n+1} + h_{n+1}) = 2g_{n+1} + 3h_{n+1}$$

$g_{n+1} = f_{n+1} - h_{n+1}$ を代入すると、

$$f_{n+2} = 2(f_{n+1} - h_{n+1}) + 3h_{n+1} = 2f_{n+1} + h_{n+1}$$

また、$h_{n+1} = g_n + h_n = f_n$ であるから、

$$f_{n+2} = 2f_{n+1} + f_n$$

(3) $a_n$ と $a_{n+1}$ の大小関係を調べる。

$a_n = \frac{f_{n+1}}{f_n}$ であるから、

$$a_{n+1} - a_n = \frac{f_{n+2}}{f_{n+1}} - \frac{f_{n+1}}{f_n} = \frac{2f_{n+1} + f_n}{f_{n+1}} - \frac{f_{n+1}}{f_n} = 2 + \frac{f_n}{f_{n+1}} - \frac{f_{n+1}}{f_n} = 2 + \frac{1}{a_n} - a_n$$

$a_{n+1} - a_n = \frac{-a_n^2 + 2a_n + 1}{a_n}$

$f_1 = 3$, $f_2 = 7$ より、$a_1 = \frac{f_2}{f_1} = \frac{7}{3}$

$-a_n^2 + 2a_n + 1 > 0$ を解くと、

$a^2 - 2a - 1 < 0$ より、

$\frac{2 - \sqrt{4 + 4}}{2} < a < \frac{2 + \sqrt{4 + 4}}{2}$

$1 - \sqrt{2} < a < 1 + \sqrt{2}$

$1 - \sqrt{2} \approx -0.414$, $1 + \sqrt{2} \approx 2.414$

$a_1 = \frac{7}{3} > 1 + \sqrt{2}$ より、$a_n$ は減少する。

$f_{n+2} = 2f_{n+1} + f_n$ より、$f_n > 0$ であるので、$a_n > 0$ である。

$a_{n+1} - a_n$ の符号は $-a_n^2 + 2a_n + 1$ の符号と同じである。

$a_n$ が単調減少で、$a_n > 0$ なので、どこかで $a_n < 1 + \sqrt{2}$ となる。

3. 最終的な答え

(1) $g_{n+1} = g_n + 2h_n$, $h_{n+1} = g_n + h_n$

(2) $f_{n+2} = 2f_{n+1} + f_n$

(3) ある $n$ までは $a_n > a_{n+1}$ で、$a_n > 1 + \sqrt{2}$ となるが、ある $n$ 以降は $a_n < a_{n+1}$ となる。ただし、$a_n < 1 + \sqrt{2}$。