大阪大学 2001年度後期・理系数学後期第1問解答・解説

問題

点 $P$ は原点から出発し、傾き $\pm 1$ の直線に沿って $x$ 座標が増える向きに格子点から格子点へ進む。ただし常に $0 ≦ y ≦ 3$ とする。 $(2 n, 0)$ に至る経路数を $a_{n}$ 、 $(2 n, 2)$ に至る経路数を $b_{n}$ とする。

(1) $a_{n + 1}, b_{n + 1}$ を $a_{n}, b_{n}$ で表せ。

(2) $a_{n} + t b_{n}$ が等比数列となる $t$ をすべて求めよ。

(3) $a_{n}, b_{n}$ の一般項を求めよ。

(4) $lim_{n \to \infty} a_{n} / b_{n}$ を求めよ。

出典：大阪大学 2001年度後期日程第2次学力試験後期・理系後期第1問

偶数の $x$ 座標では高さは0または2だけなので、この二状態の2歩遷移を数える。(2)は $(1, t)$ が遷移行列の左固有ベクトルとなる条件を立てる。二つの等比数列を連立して一般項を得る。

$x = 2 n$ で高さ0にいる経路は、次の2歩で高さ0へ1通り、高さ2へ1通り進める。高さ2にいる経路は、高さ0へ1通り、高さ2へ2通り進める。従って

a_{n + 1} = a_{n} + b_{n}, b_{n + 1} = a_{n} + 2 b_{n} .

また $x = 2$ では $a_{1} = b_{1} = 1$ である。

a_{n + 1} + t b_{n + 1} = (1 + t) a_{n} + (1 + 2 t) b_{n} .

これが $a_{n} + t b_{n}$ の定数倍になるには、その公比を $λ$ として

1 + t = λ, 1 + 2 t = λ t

が必要である。消去すると

t^{2} - t - 1 = 0.

従って

t = \frac{1 + 5}{2}, t = \frac{1 - 5}{2} .

どちらも実際に上の係数比較を満たす。

ϕ = \frac{1 + 5}{2}, ψ = \frac{1 - 5}{2}

とおく。 $1 + ϕ = ϕ^{2}$ 、 $1 + ψ = ψ^{2}$ であり、初期値から

a_{n} + ϕ b_{n} = ϕ^{2 n}, a_{n} + ψ b_{n} = ψ^{2 n} .

この二式を解くと

b_{n} = \frac{ϕ ^{2 n} - ψ ^{2 n}}{5}, a_{n} = \frac{ϕ ^{2 n - 1} - ψ ^{2 n - 1}}{5} .

$∣ ψ ∣ < 1 < ϕ$ だから

n \to \infty lim \frac{a _{n}}{b _{n}} = \frac{1}{ϕ} = \frac{5 - 1}{2} .