東北大学 2021年度後期・文系数学後期第4問解答・解説

問題

$n$ を正の整数とする。A，B，Cの3種類の文字から重複を許して $n$ 個の文字を一列に並べるとき，AとBが隣り合わない並べ方の総数を $f_{n}$ とする。たとえば $n = 2$ のとき，このような並べ方は

AA, A C, B B, B C, C A, C B, C C

の7通りあるので， $f_{2} = 7$ である。以下の問いに答えよ。

(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}$ の大小関係を調べよ。

出典：東北大学 2021年度後期日程第2次学力試験後期・文系後期第4問

方針

末尾がAまたはBである場合とCである場合に分ける。末尾がAまたはBなら次にAまたはBを置く方法は同じ文字を続ける1通りだけで，末尾がCならA,Bの2通りを置ける。ここから $g_{n + 1}, h_{n + 1}$ を出し， $f_{n} = g_{n} + h_{n}$ を使って $f_{n + 2} = 2 f_{n + 1} + f_{n}$ を導く。比 $a_{n} = f_{n + 1} / f_{n}$ は $a_{n + 1} = 2 + 1/ a_{n}$ を満たし，不動点 $1 + 2$ の上下に交互に現れることから大小を判定する。

解答

(1)

長さ $n$ の並べ方で，最後がAまたはBであるものを考える。最後がAなら次にAまたはCを置くことができるが，Bは置けない。最後がBなら次にBまたはCを置くことができるが，Aは置けない。したがって，最後がAまたはBである $g_{n}$ 通りから，長さ $n + 1$ で最後がAまたはBになるものは $g_{n}$ 通りである。

また最後がCである $h_{n}$ 通りからは，次にAまたはBを置く方法が2通りある。よって $g_{n + 1} = g_{n} + 2 h_{n}$ である。

一方，最後にCを置くことは，長さ $n$ のどの並べ方からも可能である。したがって $h_{n + 1} = g_{n} + h_{n}$ である。

(2)

$f_{n} = g_{n} + h_{n}$ である。(1) より $f_{n + 1} = g_{n + 1} + h_{n + 1} = 2 g_{n} + 3 h_{n}$ である。さらに

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

である。一方 $2 f_{n + 1} + f_{n} = 2 (2 g_{n} + 3 h_{n}) + (g_{n} + h_{n}) = 5 g_{n} + 7 h_{n}$ であるから $f_{n + 2} = 2 f_{n + 1} + f_{n}$ である。

(3)

$a_{n} = \frac{f _{n + 1}}{f _{n}}$ とおく。(2) より

a_{n + 1} = \frac{f _{n + 2}}{f _{n + 1}} = \frac{2 f _{n + 1} + f _{n}}{f _{n + 1}} = 2 + \frac{1}{a _{n}}

である。

また $f_{1} = 3$ ， $f_{2} = 7$ なので $a_{1} = \frac{7}{3}$ である。ここで $α = 1 + 2$ とおくと， $α$ は $α = 2 + \frac{1}{α}$ を満たす。さらに $a_{1} = \frac{7}{3} < 1 + 2 = α$ である。

関数 $φ (x) = 2 + \frac{1}{x}$ は $x > 0$ で単調減少であり， $α$ を不動点にもつ。したがって $a_{n} < α$ なら $a_{n + 1} > α$ ， $a_{n} > α$ なら $a_{n + 1} < α$ である。よって帰納的に $n が奇数のとき a_{n} < α, n が偶数のとき a_{n} > α$ である。

最後に $a_{n + 1} - a_{n} = 2 + \frac{1}{a _{n}} - a_{n}$ である。右辺は $a_{n} < α$ のとき正， $a_{n} > α$ のとき負である。したがって $n が奇数のとき a_{n} < a_{n + 1}, n が偶数のとき a_{n} > a_{n + 1}$ である。

東北大学 2021年度後期・文系数学 後期 第4問

問題

方針

解答

(1)

(2)

(3)

東北大学 2021年度
後期・文系数学後期第4問