15段の階段の上り方
「コマネチ大学を聴講してみた」（404 Blog Not Found）経由で見た問題。「たけしのコマネチ大学数学科」で出ていた問題だそうです。
15段の階段があります。階段を一段づつ上ってもOK、一段飛ばしで上ってもOKとして、この階段の上り方が何通りあるか答えなさい。
答そのものは弾さんのところで987通りと出せるようになっていますが、なぜこの答になるんでしょう？
階段が1段のところから順番に考えてみるとうまく行きそうです。
1段のとき（a1）：
これは考えるまでもなく上り方は1通り。（a1=1）
2段のとき（a2）：
この場合は1段ずつ2歩で上る上り方と2段を（1段飛ばしで）1歩で上る上り方の2通り。（a2=2）
3段のとき（a3）：
ここからは場合分けして考えます。
（1）最初に1段上る場合、残りの階段数が2段。2段の階段の上り方は（a2）より2通り。
（2）最初に2段上る場合、残りの階段数は1段。1段の階段の上り方は（a1）より1通り。
したがって、3段の階段の上り方は2+1で3通り。（a3=a2+a1）
4段のとき（a4）：
これも場合分けして考えます。
（1）最初に1段上る場合、残りの階段数が3段。3段の階段の上り方は（a3）より3通り。
（2）最初に2段上る場合、残りの階段数が2段。2段の階段の上り方は（a2）より2通り。
したがって、4段の階段の上り方は3+2で5通り。（a4=a3+a2）
5段のとき（a5）：
このあたりまで来るとパターンが見えてきますね。
（1）最初に1段上る場合、残りの階段数が4段。4段の階段の上り方は（a4）より5通り。
（2）最初に2段上る場合、残りの階段数が3段。3段の階段の上り方は（a3）より3通り。
したがって、5段の階段の上り方は5+3で8通り。（a5=a4+a3）
というわけで、あとは帰納法よりn段の階段の上り方はn-1段の階段の上り方とn-2段の階段の上り方を足し合わせたものになります。いわゆるフィボナッチ数列ですね。15段くらいであれば、順繰りに足していくことで987通りという答にたどり着くことができます。
が、普通に数えるとやっぱり数え損ねますよね。このパターンの問題をやったことがあればともかく、何の準備もなく現場でフィボナッチ数列に気がつくのは相当難しいでしょうね、私はできなかっただろうなぁ。
