xy 平面上を次の規則(i)，(ii)に従って移動する点 \mathrm{A} を考える。
(i) 時刻 0 で点 \mathrm{A} は原点にある。
(ii) ある時刻において点 \mathrm{A} が (x,\ y) にあるとき，時刻が 1 増えると点 \mathrm{A} は 3 点 (x+1,\ y)，(x+1,\ y+1)，(x,\ y+1) のいずれかにそれぞれ \dfrac{1}{3} の確率で移動する。
1 以上の整数 n に対して，次の条件(＊)が成り立つ確率を P_n とする。
(＊) 時刻 0 から時刻 n まで点 \mathrm{A} はつねに -1 \leqq y-x \leqq 1 で定まる領域にある。
このとき，以下の問いに答えよ。
(1) P_1，P_2，P_3 を求めよ。
(2) 1 以上の整数 n に対して，条件(＊)が成り立ちかつ時刻 n で点 \mathrm{A} が直線 y-x = 0 上にある確率を a_n とする。また，条件(＊)が成り立ちかつ時刻 n で点 \mathrm{A} が直線 y-x = 1 上または直線 y-x = -1 上にある確率を b_n とする。a_{n+1}，b_{n+1} を a_n，b_n を用いて表せ。
(3) P_{n+2} を P_{n+1}，P_n を用いて表せ。
(4) \alpha = \dfrac{1+\sqrt{2}}{3} とおくとき，P_n \leqq \alpha^{n-1} が 1 以上のすべての整数 n に対して成り立つことを証明せよ。
d = y-x とおくと、3 通りの移動で d は -1、0、+1 だけ変わり、どれも確率は \dfrac{1}{3} です。条件(＊)は、時刻 0 から n まで d が -1、0、1 のどれかにとどまることと同じになる。
d = 0 からはどう動いても範囲に残り、d = \pm 1 からは \dfrac{1}{3} の確率で外へ出る。時刻 0 で d = 0 だから P_1 = 1 で、2 回目に外へ出るのは 1 回目に \pm 1 へ動いた \dfrac{2}{3} のうちの \dfrac{1}{3} なので、P_2 = 1-\dfrac{2}{9} = \dfrac{7}{9} です。
時刻 2 で d = 0 にいる確率は \dfrac{1}{3}、d = \pm 1 にいる確率は \dfrac{4}{9} になる。3 回目に外へ出るのはこの \dfrac{4}{9} のうちの \dfrac{1}{3} だから、P_3 = \dfrac{7}{9}-\dfrac{4}{27} = \dfrac{17}{27}。
時刻 n+1 で d = 0 にいるのは、時刻 n で d = 0 にいて d を変えない移動をしたときと、d = \pm 1 にいて 0 の側へ動いたときです。どちらも確率は \dfrac{1}{3} で、a_{n+1} = \dfrac{1}{3}a_n+\dfrac{1}{3}b_n となる。
時刻 n+1 で d = \pm 1 にいる確率は、d = 0 から \pm 1 のどちらかへ動く \dfrac{2}{3} と、d = \pm 1 にいて d を変えない \dfrac{1}{3} を合わせて、b_{n+1} = \dfrac{2}{3}a_n+\dfrac{1}{3}b_n です。
d = \pm 1 から外へ出る \dfrac{1}{3} の分は、どちらの式にも数えない。
P_n = a_n+b_n で、(2) の 2 つの式を足すと P_{n+1} = a_n+\dfrac{2}{3}b_n です。n を 1 つ進めた P_{n+2} = a_{n+1}+\dfrac{2}{3}b_{n+1} に (2) を代入すると、P_{n+2} = \dfrac{7a_n+5b_n}{9} となる。
\dfrac{7a_n+5b_n}{9} = x\left(a_n+\dfrac{2}{3}b_n\right)+y(a_n+b_n) となる x、y を係数の比較で求めると、x = \dfrac{2}{3}、y = \dfrac{1}{9}。これで P_{n+2} = \dfrac{2}{3}P_{n+1}+\dfrac{1}{9}P_n が得られます。
n = 1 を代入すると P_3 =\dfrac{2}{3} \cdot \dfrac{7}{9}+\dfrac{1}{9} \cdot 1 = \dfrac{17}{27} で、(1) の値と一致する。
\alpha = \dfrac{1+\sqrt{2}}{3} は 9x^2-6x-1 = 0 の解で、\alpha^2 = \dfrac{2}{3}\alpha+\dfrac{1}{9} を満たします。(3) の漸化式と同じ係数 \dfrac{2}{3}、\dfrac{1}{9} がここにも現れる。
n = 1、2 では P_1 = 1 = \alpha^0、P_2 = \dfrac{7}{9} \leqq \alpha が成り立つ。\dfrac{7}{9} \leqq \dfrac{1+\sqrt{2}}{3} は \dfrac{4}{3} \leqq \sqrt{2} と同じで、両辺を 2 乗した \dfrac{16}{9} \leqq 2 から正しいとわかります。
P_n \leqq \alpha^{n-1} と P_{n+1} \leqq \alpha^n を仮定する。(3) の係数はどちらも正だから、P_{n+2} \leqq \dfrac{2}{3}\alpha^n+\dfrac{1}{9}\alpha^{n-1} = \alpha^{n-1}\left(\dfrac{2}{3}\alpha+\dfrac{1}{9}\right) = \alpha^{n+1} です。
n と n+1 で成り立てば n+2 でも成り立つため、n = 1、2 から順に、1 以上のすべての整数 n で P_n \leqq \alpha^{n-1} が成り立つ。