フィボナッチ数列の出現★

0と1だけが並んでいる語を考えます．そのようなn桁の語をn-bit語と呼びます．
連続して1を含まないn-bit語はいくつあるでしょうか．
(1)n=1のとき，そのような語は，0,　1,ですから，計2個あります．
これをa(1)=2と書きます．
(2)n=2のとき，そのような語は，00,　01,　10で，a(2)=3個です．
11は1が連続するので条件に合いません．
(3)n=3のとき，そのような語は，
n=2のときの語の末尾に0を付加した，000,　010,　100，のa(2)個，
および，n=2のときの末尾に1を付加したものと言いたいところですが，
１の連続を避けるために，n=1のときの語に01を付加し，001,　101のa(1)個で，
互いに背反するこの両ケースを合わせて，a(3)=a(2)+a(1)=5です．

連続した1のない語の数の数列a(n)は，このような手順（一般のnで成立）で作れ，
2,3,5,･････と続き，a(n)=a(n-1)＋a(n-2)が得られます．
これはフィボナッチ数列の再帰的な定義そのものです．
フィボナッチ数列F(n)は，1,1,2,3,5,･････ですから，
a(n)は3項目から始まるフィボナッチ数列です．a(n)=F(n+2)

それでは，連続した111を含まないn-bit語の数はいくつでしょうか．
これも同様な議論で，a(n)=a(n-1)+a(n-2)+a(n-3)　となることが証明できます．

（問題）n個のコインを順番に投げて，連続して表がでない確率を求めよ．
（解）連続して表の出ないに相当する語の数はa(n)=F(n+2)でした．
n個のコインを順番に投げて実現する状態数は2ⁿですから，求める確率はF(n+2)/2ⁿとなります．