娘とフィボナッチ数列

フィボナッチ数列について少し検索してみたところ、「すぐる学習会」という塾に
大変おもしろいまとめページがあった。
（リンクしていいかどうかわかりませんのでURLは書きませんが、検索すればすぐ
　出てくると思います。）
その中に、東京女学館中学の入試問題として、次のような問題があった。
　
　階段を上るのに1度に1段または2段で上る。
　(1) 4段上る方法は何通りあるか？
　(2) 7段上る方法は何通りあるか？
　
こんな問題、確かに聞いたことはある。
しかし、これがフィボナッチ数列になるとは知らなかった（気がつかなかった）。
　
さっそく、娘とやってみた。
（高校生の息子は、問題を言うと鼻で笑っただけだったので、
　「答がフィボナッチ数列になるんだぞ」と言うと、神妙な顔をして
　「なるほど、おもしろいね」。
　ま、それだけでわかったようなので、それ以上、話さなかった。）
まあ、基本は、場合分けではないだろうか。たとえば、(2)なら、
　・すべて1段で上る　→　1通り
　・1回だけ2段上りを入れる　→　6通り（6C1）
　・2回だけ2段上りを入れる　→　10通り（5C2）
　・3回だけ2段上りを入れる　→　4通り（4C3）
で合計21通りになる。
　
娘と一緒に、階段が1段の場合、2段の場合、3段の場合、4段の場合（ここまでは
手でやれる）、7段の場合、8段の場合（こっちは場合の数）を計算して、
表にまとめてみた。
1段目 1通り、2段目 2通り、3段目 3通り、4段目 5通り、7段目 21通り、8段目 34通り。
すると、娘は目を輝かせて、「あ、これ、こないだやったやつ。フィボナッチ数列だ！」。
そうだよね。お父さん、本当にうれしかったよ。
　
それで、どうしてフィボナッチ数列になるかも考えた。
n 段目に行くには、n - 2 段目から行くか、n - 1 段目から行くしかないからだよね。
それもちゃんとわかった様子。
いや〜、楽しいなぁ。
すぐる学習会さん、東京女学館中学さん、ありがとうございます。