解説

方針・初手

表を $H$、裏を $T$ と書く。

ちょうど $n$ 回目で終了するには、最後の2回が $HH$ であり、それ以前には $HH$ が現れていない必要がある。特に $n \geqq 3$ のとき、最後の3回は必ず $THH$ である。

そこで、連続する $HH$ を含まない列の個数を数えて、漸化式を作る。

解法1

長さ $m$ の $H,T$ の列のうち、連続する $HH$ を含まないものの個数を $a_m$ とする。ただし、空列も1通りと考え、$a_0=1$ とする。

長さ $m$ の列を最後の文字で分ける。

最後が $T$ の場合、その前の $m-1$ 文字は任意の「$HH$ を含まない列」でよいから $a_{m-1}$ 通りである。

最後が $H$ の場合、その直前は $T$ でなければならない。したがって末尾は $TH$ となり、その前の $m-2$ 文字は任意の「$HH$ を含まない列」でよいから $a_{m-2}$ 通りである。

よって $m \geqq 2$ について

$$ a_m=a_{m-1}+a_{m-2}

$$

が成り立つ。

また、

$$ a_0=1,\qquad a_1=2

$$

である。

（1） まず $P_2,P_3,P_4$ を求める。

2回目で終了するのは $HH$ のみであるから、

$$ P_2=\frac{1}{4}

$$

である。

3回目で終了するには $THH$ のみであるから、

$$ P_3=\frac{1}{8}

$$

である。

4回目で終了するには、最後の3回が $THH$ であり、最初の1回は $H,T$ のどちらでもよい。したがって

$$ HTHH,\quad TTHH

$$

の2通りであるから、

$$ P_4=\frac{2}{16}=\frac{1}{8}

$$

である。

**(2)**

$n \geqq 3$ のとき、ちょうど $n$ 回目で終了する列は、最後の3回が $THH$ であり、その前の $n-3$ 回は $HH$ を含まない列である。

したがって

$$ P_n=\frac{a_{n-3}}{2^n}

$$

である。

同様に、

$$ P_{n+1}=\frac{a_{n-2}}{2^{n+1}}

$$

である。ここで

$$ a_{n-2}=a_{n-3}+a_{n-4}

$$

より、

$$ \begin{aligned} P_{n+1} &=\frac{a_{n-3}+a_{n-4}}{2^{n+1}}\\ &=\frac{1}{2}\cdot \frac{a_{n-3}}{2^n} +\frac{1}{4}\cdot \frac{a_{n-4}}{2^{n-1}}\\ &=\frac{1}{2}P_n+\frac{1}{4}P_{n-1} \end{aligned}

$$

となる。よって、$n \geqq 3$ に対して

$$ P_{n+1}=\frac{1}{2}P_n+\frac{1}{4}P_{n-1}

$$

である。

**(3)**

$n \geqq 2$ に対して

$$ \frac{P_n}{2}\leqq P_{n+1}\leqq P_n

$$

を示す。

まず $n=2$ のとき、

$$ P_2=\frac{1}{4},\qquad P_3=\frac{1}{8}

$$

であるから、

$$ \frac{P_2}{2}=P_3\leqq P_2

$$

となり、成り立つ。

次に、ある $n \geqq 3$ について

$$ \frac{P_{n-1}}{2}\leqq P_n

$$

が成り立つと仮定する。

(2) の漸化式より、

$$ P_{n+1}=\frac{1}{2}P_n+\frac{1}{4}P_{n-1}

$$

である。

まず $P_{n-1}\geqq 0$ より、

$$ P_{n+1}=\frac{1}{2}P_n+\frac{1}{4}P_{n-1}\geqq \frac{1}{2}P_n

$$

である。

また、仮定 $\dfrac{P_{n-1}}{2}\leqq P_n$ より $P_{n-1}\leqq 2P_n$ であるから、

$$ P_{n+1} =\frac{1}{2}P_n+\frac{1}{4}P_{n-1} \leqq \frac{1}{2}P_n+\frac{1}{4}\cdot 2P_n =P_n

$$

となる。

したがって

$$ \frac{P_n}{2}\leqq P_{n+1}\leqq P_n

$$

が成り立つ。以上より、数学的帰納法により、すべての $n \geqq 2$ で

$$ \frac{P_n}{2}\leqq P_{n+1}\leqq P_n

$$

が成り立つ。

解説

この問題の要点は、「初めて $HH$ が出る」という条件を、最後の形とそれ以前の制限に分けることである。

$n \geqq 3$ でちょうど $n$ 回目に終了するなら、最後の2回は $HH$ であり、直前の $n-2$ 回目は $H$ ではあり得ない。もし $n-2$ 回目も $H$ なら、$n-1$ 回目までにすでに $HH$ が出ているからである。したがって末尾は必ず $THH$ になる。

その前の部分は「$HH$ を含まない列」を数えればよいので、フィボナッチ型の漸化式が現れる。確率 $P_n$ そのものは各列の確率 $2^{-n}$ が付くため、個数の漸化式から

$$ P_{n+1}=\frac{1}{2}P_n+\frac{1}{4}P_{n-1}

$$

という形になる。

不等式は、この漸化式を使うと自然に示せる。下側の評価は $P_{n-1}\geqq 0$ からすぐに出る。上側の評価には、1つ前の下側の評価 $P_n\geqq \dfrac{P_{n-1}}{2}$ を使うのがポイントである。

答え

**(1)**

$$ P_2=\frac{1}{4},\qquad P_3=\frac{1}{8},\qquad P_4=\frac{1}{8}

$$

**(2)**

$n \geqq 3$ に対して

$$ P_{n+1}=\frac{1}{2}P_n+\frac{1}{4}P_{n-1}

$$

**(3)**

$n \geqq 2$ に対して

$$ \frac{P_n}{2}\leqq P_{n+1}\leqq P_n

$$

が成り立つ。