18/07/22 11:31:54.27 Ug1/d9Qd.net
>>682
[京大2007理乙-1(1)]
3項間漸化式を立てる
n段の階段の昇り方をa_n通りとすると
a_1=1,a_2=2,a_3=3
n≧4で
i) 最初に1段昇ったとき
残りn-1段の昇り方はa_(n-1)通り
ii) 最初に2段昇ったとき
条件より次の1歩は必ず1段昇る
残りn-3段の昇り方はa_(n-3)通り
よってa_n=a_(n-1)+a_(n-3)
a_4=a_3+a_1=3+1=4
a_5=a_4+a_2=4+2=6
a_6=a_5+a_3=6+3=9
…
a_15=a_14+a_12=189+88=277
277通り
「1歩で2段昇ることは連続しない」という条件がなければ
(a_0=1,)a_1=1,a_(n-2)=2
a_n=a_(n-1)+a_(n-2)
でありフィボナッチ数列になる
階段の昇り方の問題は青チャにも載ってたはず