システム管理者
$$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$$となります．
練習問題
Q：
1ドル札と2ドル札のみを使い，$$n$$（整数）ドルを払う方法の数$$B(n)$$を求めましょう．（同じ種類の札は区別しませんが，札の出る順番は区別します）
A：
１．$$n=$$1のとき：2ドル札は0枚で，1ドル札1枚出すしか方法はありません：
方法$$｛1｝$$のみで，方法の数は$$B(1)=1$$
２．n=2のとき：2ドル札0枚なら｛1,1｝，2ドル札1枚なら{2}で，
方法の数は B(2)=2
３．n=3のとき：2ドル札0枚なら｛1,1,1｝，2ドル札1枚なら｛2,1}，{1,2}で，
方法の数は B(3)=3
４．n=4のとき：2ドル札0枚なら{1,1,1,1}，2ドル札1枚なら{2,1,1},{1,2,1},{1,1,2}，2ドル札2枚なら{2,2}で，
方法の数は B(4)=5
（注意）同じ種類の札は区別しませんが，違う種類の札が出る順番は区別しています）
これらの結果を考察すると，
B(n)はB(n-1)の方法に1ドル追加したものと，B(n-2)の方法に2ドル追加するものとの和になる．
2ドル追加の方法に{1,1}を追加する方法があると思う人がいるかもしれないが，追加する２つの１のうちの始めの１は，B(n-1)個の方法に繰り込まれ，すでに存在し，それに1を追加することは，すでに前者の項に含まれている．ゆえに．
B(n)=B(n-1)+B(n-2)
かくして，この方法でnドル支払う方法の数の再帰的な定義が得られました．
これはフィボナッチ数列
1, 2, 3, 5, 8, 13, 21, 34, 55, ･････
の定義と同じです．
(注)この記事は，Fibonacci and Lucas Numbers with Applications, Thomas Koshy, Wiley, Ch.4 を参考にしました．