2大分大学 2020年 数学 第2問解答・解説

大問2（階段の上り方）

(1) n段を上る方法の数を $a_n$ とする。最初の一歩が1段なら残りは $n-1$ 段、2段なら残りは $n-2$ 段なので、$n\geq3$ で $$a_n=a_{n-1}+a_{n-2}.$$ $a_1=1$、$a_2=2$ から順に計算すると、$a_3=3,a_4=5,a_5=8,a_6=13,a_7=21,a_8=34,a_9=55,a_{10}=89$。したがって **89通り**。

(2) 正の整数 $n$ に対し、$a_1=1,a_2=2$ および $n\geq3$ で $a_n=a_{n-1}+a_{n-2}$ と定めれば、求める方法数は $a_n$ である。フィボナッチ数列を $F_1=F_2=1,\ F_{m+2}=F_{m+1}+F_m$ と定めると、初期値が一致し、同じ漸化式を満たすので $a_n=F_{n+1}$。よって答えは **$F_{n+1}$ 通り**（同値に、上記の漸化式と初期値で定まる数）。また、2段進む回数が $j$ 回なら1段進む回数は $n-2j$ 回で、全部の動作は $n-j$ 回である。その中から2段進む $j$ 回の位置を選ぶので、方法数は $\displaystyle \binom{n-j}{j}$ 通り。$0\le j\le\lfloor n/2\rfloor$ を足し合わせると $$\displaystyle a_n=\sum\limits _{j=0}^{\lfloor n/2\rfloor}\binom{n-j}{j}.$$ これは $n$ から直接計算できる式であり、(1)の $n=10$ では $1+9+28+35+15+1=89$ と一致する。