有名な問題です。
できるようにしたい。
問題
階段の一段を一歩で一段または2段または3段のぼります。たとえば，ちょうど3段のぼる方法は1＋1＋1段，1＋2段，2＋1段，3段の4通りあります。ちょうど6段のぼる方法は何通りありますか。
解説
ちょうど4段のぼるときを考えます。
4段目に着く一歩前が1段目のとき、3段のぼる登り方なので4通り、2段目のときは2段のぼる登り方なので、1＋1段、2段の2通り、3段目のときは1段なので1通りです。つまり、合計は1＋2＋4＝7通りです。
5段のぼるときは、1歩目が1段目、2段目、3段目なので、7＋4＋2＝13通り、6段のぼるときも同様に13＋7＋4＝24通りです。
24通り