問題
15段の階段を上るとき、1段上るか、2段上るか、2通りの方法を組み合わせて登ると、何通りの登り方があるか。
イズミの解答への道
いきなり15段を考えるのは難しいので、少ない数から考えてみましょう。数学では、このように、
「少ない数で試す」
ことは非常に大事な考え方です。
まずは3段ではどうでしょうか。3段の登り方だったらすべて数えられます。
- 1段 – 1段 – 1段
- 2段 – 1段
- 1段 – 2段
の3通りです。ここで1つブレイクスルーが必要です。それは「最後に登るのが何段か」、いいかえれば「何段手前から登ってきたか」に着目するということです。
どのような場合でも最後の登り方は1段か2段です。3段目にたどりつくには、1段目から登るかか、2段目から登るかのどちらかしかないということです。さきほどの例でいえば、
（1段 – 1段）- 1段
（2段） – 1段
1段 – 2段
のように見て、（ ）の部分は別途考えるということです。なぜなら、（ ）の部分は2段登る方法が何通りかという、言ってしまえば別の問題だからです。
また、このように考えると何段でも同じです。 10 段目に辿り着く場合の数を数えるには、 8 段目まで登る場合の数と、 9 段目に登る場合の数を求めればよい、ということですし、その 8 段目に登る場合の数が知りたければ、 6 段登る方法と 7 段登る方法を調べればよいのです。ポイントは、連鎖的に関係しているということです。
さて、こういうときに使うのが漸化式（高校の数学Bで勉強します）という考え方です。一般化してみましょう。 n 段登る方法を an 通りとすれば、どのような関係式が成り立つでしょうか。
解答
（2段目以上の）ある段に達するためには、その2段手前から2段登りで到達する方法と、1段手前から1段登りで到達する方法がある。（ココがポイント☆）
つまり、（ n ≧ 3 に対して、） n 段目に達する登り方が an 通りあるとすると、
an = an-1 + an-2
とあらわされ、1段登る方法は1通り、2段登る方法は2通りなので、 a1 = 1 , a2 = 2 である。
以後、この式で計算をすすめると、
a3 = a2 + a1 = 3 , a4 = 3 + 2 = 5 , a5 = 5 + 3 = 8 , …… , a15 = 987
となり、987通りが正解である。
コメント