階段を1段または2段で昇る [2007 京都大・理乙]

 1歩で1段または2段のいずれかで階段を昇るとき、1歩で2段昇ることは連続しないものとする。15段の階段を昇る昇り方は何通りあるか。

[2007 京都大・理乙]

イズミの解答への道

有名な問題の亜流。漸化式を立てて、数えていくのが鉄則です。2段を連続しないという条件を省けば、毎年どこかの大学で出題される超有名問題で、経験がないと厳しいですが、一度見たことがあればはじめの一歩は手を出すことができるでしょう。

解答

n段の階段を問題の条件に沿うように昇る場合の数を anとすると、
  a1 = 1 , a2 = 2 , a3 = 3
となる。また、 n≧4 については最初の1段目で場合に分けると、

  • 最初を1段昇り → 残り n – 1 段を昇る方法は自由なので an-1 通り
  • 最初を2段昇り → 次は必ず1段昇りなので、残り n – 3 段を昇る方法で an-3 通り

となるので、
  an = an-1 + an-3
となり、順に計算していくと、
  a4 = a3 + a1 = 4 , a5 = 6 , … , a15 = 277
となり、277通り

解説

 このパターンの問題の最初の一手は「n段登る方法を an 通りとおく」ところである。