Fibonacci数列の出現２

練習問題
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, ･････
の定義と同じです．