は 以上の整数とする。 枚の硬貨を続けて 回投げる。このとき， 回目 に表が出たら ，裏が出たら として，，，， を定める。 とするとき， が奇数である確率 を求めよ。
は、 回目と 回目がともに表のときだけ で、ほかは です。 は、隣り合う 回がどちらも表になっている組を数えている。
たとえば表表表裏表表なら、 回目と 回目、 回目と 回目、 回目と 回目の 組で、 です。表が 回続くところは 組と数えます。
では で、奇数になるのは 回とも表のときに限り、 です。 で が奇数になるのは表表裏と裏表表の 通りで、 となる。
回投げたあとに 回つけ足すと、 です。ふえる量を、つけ足した 回の出方で分けます。
裏裏と裏表では、ふえる量は です。表裏では 、表表では だけふえる。
が でも でも、 と の片方だけが奇数になります。 通りのうち、ふえる量が奇数になるのは 通りで、それまでの出方によらず確率は です。
が奇数になるのは、 が奇数でふえる量が偶数のときと、 が偶数でふえる量が奇数のときです。つけ足した 回はそれまでの出方と独立なので、 となる。
整理すると で、両辺から を引くと です。
回ごとに、 との差が半分になっていく。 が偶数の列は から、奇数の列は から始まります。
のとき、 から 回半分にして、 です。 を入れると となる。
のときも、 から同じように半分にしていき、 です。 を入れると になります。
なら で、 通りのうち が奇数になる 通りと一致する。