連続で2段上れないときには階段の上り方は何通りあるか？

最初を0段目として\(m\)段目から\(n+m\)段目まで上る場合の数を\(A_{n}\)とする。
ただし、\(m\)段目から1段上ることも2段上ることが出来るとする。
このとき0段目から\(n+3\)段目に上るには最初の1歩が1段であと\(n+2\)段上るか、最初の1歩が2段で次に1段上ってあと\(n\)段上るかの2通りある。
これより、初期条件\(A_{0}=1,A_{1}=1,A_{2}=2\)で\(0\leq n\)のとき漸化式\(A_{n+3}=A_{n+2}+A_{n}\)となる。
従って漸化式より
\begin{align*} A_{0} & =1\\ A_{1} & =1\\ A_{2} & =2\\ A_{3} & =3\\ A_{4} & =4\\ A_{5} & =6\\ A_{6} & =9\\ A_{7} & =13\\ A_{8} & =19\\ A_{9} & =28\\ A_{10} & =41 \end{align*} となるので41通りとなる。