トップ› 九州大学› 1989年› 理系第5問

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

方針・初手

まずは $n\mathrm{km}$ コースの総数 $f_n$ が満たす漸化式を立てる。最初の $1$ 周としてどのコースを選ぶかで場合分けをすると、$f_{n+2}$ を $f_{n+1}$ と $f_n$ で表すことができる。(1) はこの漸化式が、与えられた2次方程式の解の性質と合致することを示す。(2) は隣接3項間漸化式の典型的な解法である特性方程式を利用して一般項を求める。(3) は求めた一般項から極限を計算する。対数の中身で最も発散のスピードが速い項をくくり出すのが定石である。

解法1

(1)

$n+2\mathrm{km}$ ($n \geqq 1$) のコースは、最初に走るコースによって以下の3つの場合に分けられる。

(i) 最初にコース $A$ ($1\mathrm{km}$) を走る場合残りは $n+1\mathrm{km}$ のコースとなるから、その選び方は $f_{n+1}$ 通りである。

(ii) 最初にコース $B$ ($2\mathrm{km}$) を走る場合残りは $n\mathrm{km}$ のコースとなるから、その選び方は $f_n$ 通りである。

(iii) 最初にコース $C$ ($2\mathrm{km}$) を走る場合残りは $n\mathrm{km}$ のコースとなるから、その選び方は $f_n$ 通りである。

これらは互いに排反であるから、$n \geqq 1$ において以下の漸化式が成り立つ。

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

これを整理すると、

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

となる。一方で、2次方程式 $t^2 - t - 2 = 0$ の解が $\alpha, \beta$ であるから、解と係数の関係より

$$ \alpha + \beta = 1, \quad \alpha \beta = -2 $$

が成り立つ。これを用いると、上の漸化式は次のように変形できる。

$$ f_{n+2} - (\alpha + \beta)f_{n+1} + \alpha \beta f_n = 0 $$

$$ f_{n+2} - \alpha f_{n+1} = \beta (f_{n+1} - \alpha f_n) $$

ここで、$n \geqq 2$ のとき $g_n = f_n - \alpha f_{n-1}$ とおくと、式の形から $g_{n+1} = f_{n+1} - \alpha f_n$ であるから、

$$ g_{n+1} = \beta g_n $$

が成り立つことが示された。

(2)

特性方程式 $t^2 - t - 2 = 0$ を解くと、$(t-2)(t+1) = 0$ より $t = 2, -1$ である。 $\alpha, \beta$ は対称であるから、$(\alpha, \beta) = (2, -1)$ としても一般性を失わない。

$f_1$ は $1\mathrm{km}$ のコースであり、コース $A$ を $1$ 周する $1$ 通りのみであるから $f_1 = 1$。 $f_2$ は $2\mathrm{km}$ のコースであり、$A \to A$, $B$, $C$ の $3$ 通りであるから $f_2 = 3$。

(1) より、数列 $\{g_n\}$ は公比 $\beta = -1$ の等比数列である。初項 $g_2$ は

$$ g_2 = f_2 - 2f_1 = 3 - 2 \cdot 1 = 1 $$

であるから、

$$ g_n = 1 \cdot (-1)^{n-2} = (-1)^n $$

すなわち、

$$ f_n - 2f_{n-1} = (-1)^n \cdots ① $$

が成り立つ。

次に、$\alpha$ と $\beta$ の役割を入れ替え、$(\alpha, \beta) = (-1, 2)$ として $h_n = f_n - \beta f_{n-1} = f_n - 2f_{n-1}$ とおくと、同様の議論から $h_{n+1} = \alpha h_n$、すなわち $h_{n+1} = -h_n$ が成り立つ。ここで初項 $h_2$ は、

$$ h_2 = f_2 - (-1)f_1 = 3 + 1 = 4 $$

であるから、数列 $\{h_n\}$ は公比 $2$ の等比数列となり、

$$ h_n = 4 \cdot 2^{n-2} = 2^n $$

すなわち、

$$ f_n + f_{n-1} = 2^n \cdots ② $$

が成り立つ。

$f_{n-1}$ を消去するため、① $+ 2 \times$ ② を計算すると、

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

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

これは $n=1, 2$ のときも成り立つ。

(3)

(2) で求めた $f_n$ を用いて極限を計算する。

$$ f_n = \frac{2^{n+1}}{3} \left( 1 + \frac{(-1)^n}{2^{n+1}} \right) $$

と変形し、両辺の自然対数をとると、

$$ \log f_n = \log \left\{ \frac{2^{n+1}}{3} \left( 1 + \frac{(-1)^n}{2^{n+1}} \right) \right\} $$

$$ \log f_n = (n+1) \log 2 - \log 3 + \log \left( 1 + \frac{(-1)^n}{2^{n+1}} \right) $$

となる。両辺を $n$ で割ると、

$$ \frac{\log f_n}{n} = \frac{n+1}{n} \log 2 - \frac{\log 3}{n} + \frac{1}{n} \log \left( 1 + \frac{(-1)^n}{2^{n+1}} \right) $$

ここで、$n \to \infty$ のとき、

$$ \frac{n+1}{n} = 1 + \frac{1}{n} \to 1 $$

$$ \frac{\log 3}{n} \to 0 $$

$$ \frac{(-1)^n}{2^{n+1}} \to 0 \implies \log \left( 1 + \frac{(-1)^n}{2^{n+1}} \right) \to \log 1 = 0 $$

であるから、

$$ \lim_{n \to \infty} \frac{\log f_n}{n} = 1 \cdot \log 2 - 0 + 0 = \log 2 $$

となる。

解説

場合の数の漸化式を立て、隣接3項間漸化式を解く典型問題である。「最初の1歩をどう踏み出すか」で場合分けをするのが場合の数の漸化式を立てる際の基本方針となる。特性方程式の解を用いた数列の変形は、誘導がなくても自力で実行できるようにしておく必要がある。(3) における極限計算では、分母の $n$ と相殺させるために、対数の真数部分から発散の速度が最も速い項（本問では $2^{n+1}$）をくくり出す処理が重要である。