例

5段の階段があります。１歩で１段または２段のぼってよいものとします。このとき、5段までののぼり方は全部で何通りありますか。

目のつけどころ・ヒント

①5段目までの最後の1歩も、「1段のぼり」か「2段のぼり」の２通りしかない。
②ということは、最後の1歩をのぼる前の、「2段下までののぼり方」と「1段下までののぼり方」の和となる。
③これが典型的なフィボナッチ数列。