フボナッチ数列の演習

（定義）語wordとは，順序つけられた記号の配列である．
（例）例えば，abcはアルファベット文字を用いた長さ３の語である．
001101は，バイナリー語（各ビットには，0あるいは1が入る）で，長さ6ビットである．
（注）ビットbitとは，binaryとdigitを縮めて作った造語である．

（例題）$${a_{n}}$$ を連続して1が続くことのないようなb-ビット語の数とする．$${a_{n}}$$を求めなさい．

(実験)
n=0のとき：　空集合が１つ：　$${a_{0}=1}$$
n=1のとき：　0，1　：$${a_{1}=2}$$
n=2のとき：　00，01，10　：$${a_{2}=3}$$
n=3のとき：　000，010，100，001，101　：$${a_{3}=5}$$
n=4のとき：　0000，0100，1000，0010，1010，0001，0101，1001　：$${a_{4}=8}$$

$${a_{n}}$$はフィボナッチ数列，1,2,3,5,8,....…になることが予想される．
（証明）
１．任意のn-ビット語wを考える．語wが0で終わるとすると，末尾の1つ前(n-1)番ビットは，0でも１でも良いので，この場合の1～(n-1)番ビットでできる(n-1)-ビット語の数は，$${a_{n-1}}$$個である．従って，0で終わり，連続する1を含まないn-ビット語は$${a_{n-1}}$$個である．
２．語wが1で終わるとすると，(n-1)番ビットは0でなければならない．(n-2)番ビットは何の制約もなく，0でも1でもかまわない．従って，１で終わり，連続して１を含まないn-ビット語は$${a_{n-2}}$$個ある．
1.,2.の２つのケースは互いに排他的であるので，加算原理により；
$${a_{n}=a_{n-1}+a_{n-2}}$$
これは，フィボナッチ数列の定義に他ならない．

（練習問題）
n個のコインを投げて，隣り合う２つのコインが連続して表を向くことがない確率を求めなさい．