n は 2 以上の整数とする。1 枚の硬貨を続けて n 回投げる。このとき，k 回目 (1 \leqq k \leqq n) に表が出たら X_k = 1，裏が出たら X_k = 0 として，X_1，X_2，\cdots，X_n を定める。Y_n = \displaystyle\sum_{k=2}^{n}X_{k-1}X_k とするとき，Y_n が奇数である確率 p_n を求めよ。
X_{k-1}X_k は、k-1 回目と k 回目がともに表のときだけ 1 で、ほかは 0 です。Y_n は、隣り合う 2 回がどちらも表になっている組を数えている。
たとえば表表表裏表表なら、1 回目と 2 回目、2 回目と 3 回目、5 回目と 6 回目の 3 組で、Y_6 = 3 です。表が 3 回続くところは 2 組と数えます。
n = 2 では Y_2 = X_1X_2 で、奇数になるのは 2 回とも表のときに限り、p_2 = \dfrac{1}{4} です。n = 3 で Y_3 が奇数になるのは表表裏と裏表表の 2 通りで、p_3 = \dfrac{2}{8} = \dfrac{1}{4} となる。
n 回投げたあとに 2 回つけ足すと、Y_{n+2} = Y_n+X_nX_{n+1}+X_{n+1}X_{n+2} です。ふえる量を、つけ足した 2 回の出方で分けます。
裏裏と裏表では、ふえる量は 0 です。表裏では X_n、表表では X_n+1 だけふえる。
X_n が 0 でも 1 でも、X_n と X_n+1 の片方だけが奇数になります。4 通りのうち、ふえる量が奇数になるのは 1 通りで、それまでの出方によらず確率は \dfrac{1}{4} です。
Y_{n+2} が奇数になるのは、Y_n が奇数でふえる量が偶数のときと、Y_n が偶数でふえる量が奇数のときです。つけ足した 2 回はそれまでの出方と独立なので、p_{n+2} = \dfrac{3}{4}p_n+\dfrac{1}{4}(1-p_n) となる。
整理すると p_{n+2} = \dfrac{1}{2}p_n+\dfrac{1}{4} で、両辺から \dfrac{1}{2} を引くと p_{n+2}-\dfrac{1}{2} = \dfrac{1}{2}\left(p_n-\dfrac{1}{2}\right) です。
2 回ごとに、\dfrac{1}{2} との差が半分になっていく。n が偶数の列は p_2 から、奇数の列は p_3 から始まります。
n = 2m のとき、p_2-\dfrac{1}{2} = -\dfrac{1}{4} から m-1 回半分にして、p_{2m}-\dfrac{1}{2} = -\left(\dfrac{1}{2}\right)^{m+1} です。m = \dfrac{n}{2} を入れると p_n = \dfrac{1}{2}-\left(\dfrac{1}{2}\right)^{\frac{n}{2}+1} となる。
n = 2m+1 のときも、p_3-\dfrac{1}{2} = -\dfrac{1}{4} から同じように半分にしていき、p_{2m+1} = \dfrac{1}{2}-\left(\dfrac{1}{2}\right)^{m+1} です。m = \dfrac{n-1}{2} を入れると p_n = \dfrac{1}{2}-\left(\dfrac{1}{2}\right)^{\frac{n+1}{2}} になります。
n = 4 なら \dfrac{1}{2}-\dfrac{1}{8} = \dfrac{3}{8} で、16 通りのうち Y_4 が奇数になる 6 通りと一致する。