なんでパスカルの三角形からフィボナッチが?
と思って調べたら、なるほどそういう性質があるんですね。
http://ja.wikipedia.org/wiki/%E3%83%91%E3%82%B9%E3%82%AB%E3%83%AB%E3%81%AE%E4%B8%89%E8%A7%92%E5%BD%A2だとすると、カードの枚数がx枚の時の解をa(x)とすると、
a(x) = F(x+2)-1
ですよね。F(x)はフィボナッチ数列のx番目の数です。
フィボナッチ数列には
F(x+2)=F(x+1)+F(x)
の関係がありますから、F(x+2)=a(x)+1を代入して

a(x+2)=a(x+1)+a(x)+1
の漸化式が成り立ちます。
ということは、パスカルの三角形を使わずに、最初からダイレクトに

の漸化式を導くような別解がありそうですね。
…と、漸化式から逆に考えたところ、別解が分かりました。
a(x+2)の計算を場合分けして
(i) x+2を選ばない場合が、a(x+1)通り
(ii) ややこしいのは、x+2を選ぶ場合。
この場合は、残りのカードがx+1枚で、その中から、
n以上のカードをn-1枚選ぶことになる。
カードの数字を全部1引いて0からxにしてしまえば、
n-1以上のカードをn-1枚選ぶことになる。
n>1の時はa(x)通りで、n=1の場合は1通りなので、
全部でa(x)+1通り
(i)(ii)を足したら、

の漸化式が導かれました。
と思って調べたら、なるほどそういう性質があるんですね。
http://ja.wikipedia.org/wiki/%E3%83%91%E3%82%B9%E3%82%AB%E3%83%AB%E3%81%AE%E4%B8%89%E8%A7%92%E5%BD%A2
だとすると、カードの枚数がx枚の時の解をa(x)とすると、
a(x) = F(x+2)-1
ですよね。F(x)はフィボナッチ数列のx番目の数です。
フィボナッチ数列には
F(x+2)=F(x+1)+F(x)
の関係がありますから、F(x+2)=a(x)+1を代入して
の漸化式が成り立ちます。
ということは、パスカルの三角形を使わずに、最初からダイレクトに
…と、漸化式から逆に考えたところ、別解が分かりました。
a(x+2)の計算を場合分けして
(i) x+2を選ばない場合が、a(x+1)通り
(ii) ややこしいのは、x+2を選ぶ場合。
この場合は、残りのカードがx+1枚で、その中から、
n以上のカードをn-1枚選ぶことになる。
カードの数字を全部1引いて0からxにしてしまえば、
n-1以上のカードをn-1枚選ぶことになる。
n>1の時はa(x)通りで、n=1の場合は1通りなので、
全部でa(x)+1通り
(i)(ii)を足したら、