Fibonacci数列の出現

0と1だけが並んでいる語を考えます．そのようなn桁の語をn-bit語と呼びます．
Q：連続して1を含まないn-bit語はいくつあるでしょうか？
A：
(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で成立）で作れ，a(1)＝2, a(2)＝3, a(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)

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

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

(注)この記事は，Fibonacci and Lucas Numbers with Applications, Thomas Koshy, Wiley, Ch.4 を参考にしました．