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

1ドル札と2ドル札のみを使い，n（整数）ドルを払う方法の数B(n)を求めましょう．

１．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,･････
の定義と同じです．

1,2,3の3つの数字を和の構成因子として，正の整数nを表現したとき，異なる表現数をb(n)とする．以下は例です．
1．1=1 b(1)=1
2．2=1+1=2 b(2)=2
3. 3=(1+1)+1=(2)+1=3 b(3)=3
4. 4=(1+1+1)+1=(2+1)+1=(3)+1=2+2 b(4)=4
5. 5=(1+1+1+1)+1=(2+1+1)+1=(3+1)+1＝(2+2)+1=2+3 b(5)=5
6．6=(1+1+1+1+1)+1=(2+1+1+1)+1=(3+1+1)+1＝(2+2+1)+1=(2+3)+1=3+3 b(6)=6
7．7=(1+1+1+1+1+1)+1=(2+1+1+1+1)+1=(3+1+1+1)+1＝(2+2+1+1)+1=(2+3+1)+1=(3+3)+1=3+2+2 b(7)=7

n-1の展開表現の各々に１づつ加えてnの展開表現を得るが，これに加えて，新しい表現が１つできる．従って，
b(n)=b(n-1)+1=n