階段の上り方は何通りあるか？

最初を0段目として\(n\)段目まで上る場合の数を\(A_{n}\)とする。
このとき\(n+2\)段目に上るには\(n+1\)段目から1段上るか\(n\)段目から2段上るかの2通りある。
これより、初期条件\(A_{0}=1,A_{1}=1\)で\(0\leq n\)のとき漸化式\(A_{n+2}=A_{n+1}+A_{n}\)となる。
これはフィボナッチ数列で解は
\[ A_{n}=\frac{1}{\sqrt{5}}\left\{ \left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right\} \] となるが一般項から求めるのは大変なので、漸化式から求めると、
\begin{align*} A_{0} & =1\\ 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 \end{align*} となるので89通りとなる。