ん〜、その前に、確率漸化式の解き方を説明してほしいな。

縛り、ねぇ。あんまり、イメージできないなぁ。

1歩で2段昇ることは連続しないってこと？

なるほど。それで、どうやって式を立てるの？

う〜ん。\(n-1\)段目までののぼり方を\(P(n-1)\)としちゃうと、\(n-1\)段目までに1段飛びできたのか、2段飛びできたのかわからないから、ちょっと面倒かも。

じゃあ、図を書いてみるね。

うん、こうやって書けば
$$P(n)=P(n-1)+P(n-3)$$
だってことがわかるね。

そうだね。順番にやっていくと\(P(15)=277\)だよね。

おっけい。ちょっとわかってきた。じゃあ、次の問題いこっ。

隣あった車両の少なくとも一方が赤色ってところだね。

う〜ん。今回も\(P(n)\)って置いちゃうと、\(n\)両目が赤色かどうかわからないから、やっぱりはじめの1歩かな。最初が青色か黄色なら次は赤色だし、最初が赤色なら次はなんでもいいしね。

そうだね。
$$P_{n} = P_{n-1} + 2P_{n-2}$$
かな？

特性方程式を作って、解を求めて変形する方法だね。特性方程式は
$$x^2 = x + 2$$
で、\(x=2, -1\)だから、2通りの式ができるね。
$$P_{n+2}-2P_{n+1} = -1(P_{n+1}-2P_{n})$$
$$P_{n+2}+P_{n+1} = 2(P_{n+1}+P_{n})$$
ここで、\(P(1) = 3, P(2) = 5, P(3) = 11\)ということを使って、上側 を解いて
$$P_{n+1}-2P_{n} = (-1)^{n-1}(P_{2}-2P_{1}) = (-1)^{n}$$
下側を解いて、
$$P_{n+1}+P_{n} = 2^{n-1}(P_{2}+P_{1}) = 2^{n+2}$$
あとは、\(P_{n+1}\)を消去すればいいんだね。

$$P_{n} = \frac{2^{n+2}-(-1)^{n}}{3}$$
かな。え〜と、それで、\(n=2\)の時の確認が必要なんだよね？
式に代入すると、5通りで、実際に調べても5通りだから、この式は\(n\geq2\)で成り立つ式だね！

まだまだ！　次はないの？

ようやく、最後の一歩で場合分け、ていう問題だね。今まで通り、図を書いて調べてみよっか。

この図から、\(a_{n}, b_{n}, c_{n}\)と\(a_{n-1}, b_{n-1}, c_{n-1}\)の関係を読み取ってみるね。問題の条件から、
1. AとBの札のスイッチは\(\frac{1}{3}\)
2. AとCの札のスイッチは\(\frac{2}{3}\)
だね。そうすると
$$a_{n} = \frac{1}{3}b_{n-1}+\frac{2}{3}c_{n-1}$$
$$b_{n} = \frac{1}{3}a_{n-1}+\frac{2}{3}b_{n-1}$$
$$c_{n} = \frac{2}{3}a_{n-1}+\frac{1}{3}c_{n-1}$$
かな。

でも、ちょっと複雑だなぁ。これどうやって解くの？

もう一つ？　ある？

あっ、そうか、全部足すと、そりゃ、1だよね。

じゃあ、これで、\(a_{n}\)の式から\(b_{n}\)を消してみようかな。そうすると
$$3a_{n} = 1-a_{n-1}+c_{n-1}$$
$$c_{n-1} = 3a_{n}+a_{n-1}-1$$
$$c_{n} = 3a_{n+1}+a_{n}-1$$
だから、、、これを\(c_{n}\)の式に代入すれば、\(a_{n}\)だけになるね。結果は
\(a_{n+1} = \frac{1}{3}a_{n-1}+\frac{2}{9}\)だ！

1個飛ばしは「偶奇に分けよ」

いや、別になんでもないんだけど。とにかく、\(n\)を偶数、奇数に分ける必要があるね。まずは偶数の場合。\(n = 2k\)(\(k\)は自然数)とおくよ。
$$a_{2(k+1)} = \frac{1}{3}a_{2k}+\frac{2}{9}$$
この形は特性方程式で\(\alpha\)を求めればいいね。
$$\alpha = \frac{1}{3}\alpha + \frac{2}{9}$$
から\(\alpha = \frac{1}{3}\)だとわかるから、
$$a_{2(k+1)}-\frac{1}{3} = \frac{1}{3}\left( a_{2k} – \frac{1}{3}\right)$$
と変形できるね。\(a_{1} = 0, a_{2} = \frac{5}{9}\)を使うと、
$$a_{2k} – \frac{1}{3} = \left(\frac{1}{3}\right)^{k-1}\cdot\frac{2}{9} $$
$$a_{2k} = \frac{1}{3} + \frac{2}{3^{k+1}}$$

おっけい。じゃあ、次は奇数ね。奇数はn=2k-1とおくけど、特性方程式の解は同じだから、結局
$$a_{2(k+1)-1}-\frac{1}{3} = \frac{1}{3}\left( a_{2k-1} – \frac{1}{3}\right)$$
まではほとんど同じだね。違うのは、初項だけだから、
$$a_{2k-1} – \frac{1}{3} = \left(\frac{1}{3}\right)^{k-1}\cdot\left(-\frac{1}{3} \right)$$
となって、
$$a_{2k-1} = \frac{1}{3}-\left(\frac{1}{3}\right)^{k}$$
今回は、\(k = \frac{n+1}{2}\)を使って
$$a_{n} = \frac{1}{3}-\left(\frac{1}{3}\right)^{\frac{n+1}{2}}$$
ただし、\(n\)は奇数
どうだ！

??????
え〜と、どうなってるのかな？　これ。

まず、さいころを振るでしょ。それで目が出て、それを\(X\)と置く。そのあと、\(Y\)を計算して、\(Y\)の値の範囲を調べる。それで、またさいころを振る。この繰り返しだね。

え〜と、うん。縛りを探せ、ってことでしょ。今回こそ、露骨な縛りがあるよ。
$$Y_{k} = X_{k} + \frac{1}{Y_{k-1}}$$
っていう漸化式だね。

じゃあ、次は最初の一歩か最後の一歩か、どっちかを考えなきゃね。私流の方法は、最後の一歩で試してダメだったら、最初の一歩に持っていくって方法だけど、今回は、\(n-1\)回目までを\(p_{n-1}\)とおいてしまって大丈夫そうだね。だから、最後の一歩で場合分けだ！

え？　違うの？

あ、いつもの仕返しだね〜。おっけい。じゃあ、やってみるよ。とりあえず、\(n-1\)回目までに、\(Y_{n}\)が条件を満たしている場合と、満たしていない場合の2通りがあって、満たしていない場合は、さらに、不等式の下側にある場合と上側にある場合で、合計3通りあるから、一つずつ図を書いてみるよ。

ゆっくり進めていくね。まず、\(Y_{n-1}\)が条件を満たしているとき。この時に、\(Y_{n}\)がさらに条件を満たすような\(X_{n}\)が何通りあるかを考えればいいわけだから、\(Y_{n} = X_{n}+\frac{1}{Y_{n-1}}\)を使って計算すればいいよね。一つずつ代入していけば良さそうだけど、\(X_{n}=3\)を代入したとき、\(Y_{n}\)の不等式の左の値が\(1+\sqrt{3}\)を超えちゃうから、それ以上の\(X_{n}\)を入れてもダメだね。だから、この場合は\(X_{n}=1, 2\)の2通りあるってことか。

じゃあ、次は、\(Y_{n-1}\)が条件を満たしていないとき。特に、不等式の左側にある場合を考えるよ。

あ、それは、\(Y_{n} = X_{n}+\frac{1}{Y_{n-1}}\)の式からだよ。それと、\(X_{1}=Y_{1}\)だね。\(X_{n}\)、つまり\(n\)回目のさいころの出目の最小値が1だからね。この場合は、\(X_{n}\geq 2\)の時にはもう、\(Y_{n}\)の条件を満たさないことがわかる。だから、\(X_{n}=1\)の1通りしかないね。

じゃあ、最後のパターンね。

うん。まぁ、式の形から、負になることはないよね。この場合は、上の図に書いた通り、\(X_{2} = 2\)のときだけOKだね。これは嬉しい結果よね。だって、\(Y_{n}\)が条件を満たしていないときは、両方とも\(X_{n}\)が1通りしかないんだもん。

\(Y_{n-1}\)が条件を満たす確率は\(p_{n-1}\)と置けるし、\(Y_{n-1}\)が条件を満たさない確率は\(1-p_{n-1}\)と置けるね。あ！　これなら、すぐに漸化式を作れるんだ。

そうだね。今だったら
$$p_{n} = \frac{1}{3}p_{n-1} + \frac{1}{6}(1-p_{n-1}) = \frac{1}{6}p_{n-1}+\frac{1}{6}$$
ってわかるもんね！　ちなみに、\(p_{1} = \frac{1}{6}\)だね。
$$p_{n+1} = \frac{1}{6}p_{n}+\frac{1}{6}$$
としてもいいんだよね。

うん。あとは特性方程式を解いて、計算だ。特性方程式を解いて変形すると、
$$p_{n+1}-\frac{1}{5} = \frac{1}{6}\left(p_{n} – \frac{1}{5}\right)$$
だから、これを解いて、
$$p_{n} = \frac{1}{5} – \frac{1}{5}\left(\frac{1}{6}\right)^{n} = \frac{1}{5}\left( 1-\frac{1}{6^{n}} \right)$$
かな？

あ、そうか。勉強になります！

そんなことないよ〜。まみが教えてくれたことをそのまま当てはめてみただけだからね。わかりやすかったよ！

最後は、まみがまとめてよ。

あとは、漸化式を解くパターンは一通り身につけていないとダメだね。せっかく漸化式ができたのに、解けませんでした、じゃ悲しいもんね。

でも、まみのおかげで解き方のコツを掴んだ気がする。ありがと！