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

イズミの解答への道

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

解答

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

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

解説

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