コインをn回投げたとき、表が3回連続で出ないような場合の数を$a_n$とする。

「$n \geqq 4$ のとき, $n$ 回投げて3回連続で表が出ない」・・・（★）

以下のように「最初の3回がどうだったか？」に注目して場合分けをします。

（★）のためには、

(1) 1回目が裏の場合

残りの $n-1$ 回について3回連続で表が出なければ良い。

(2) 1回目が表の場合

以下のように場合分けする。

(2)-1. 2回目が裏の場合

残りの $n-2$ 回について3回連続で表が出なければ良い。

(2)-2. 2回目が表の場合

3回目は裏で、残りの $n-3$ 回について3回連続で表が出なければ良い。

逆に、上記以外の場合は（★）を満たさない。

したがって漸化式は

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

となります。

漸化式は $n-1$, $n-2$ 回目はどんな状態だったか？に着目することが多いですが、この発想で苦しい場合は逆に1回目,2回目で場合わけをするとうまくいく場合があります。