場合の数を3項間の漸化式で求める（A）

$n$ 段の階段を上る方法を $a_n$ 通りとする．$n+2$ 段上る方法は，最後の 1 歩で \begin{itemize} \item 1 段上る場合：その前に $n+1$ 段上っているから $a_{n+1}$ 通り \item 2 段上る場合：その前に $n$ 段上っているから $a_n$ 通り \end{itemize} があり，これらは重ならない（下図）．よって \[ a_{n+2}=a_{n+1}+a_n,\qquad 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 通り