解説

方針・初手

最後の1歩に注目する。$n$段目に到達する直前は、$n-1$段目、$n-2$段目、$n-3$段目のいずれかである。したがって、登り方の総数はこれら3つの場合の和で表せる。

解法1

$n$段の階段を登るとき、最後の1歩として考えられるのは次の3通りである。

（i） 最後に1段上る場合

この直前には $n-1$ 段目まで登っている。したがって、この場合の登り方は $a_{n-1}$ 通りである。

（ii） 最後に2段上る場合

この直前には $n-2$ 段目まで登っている。したがって、この場合の登り方は $a_{n-2}$ 通りである。

（iii） 最後に3段上る場合

この直前には $n-3$ 段目まで登っている。したがって、この場合の登り方は $a_{n-3}$ 通りである。

これらは最後の1歩の段数が異なるため重複せず、すべての場合を尽くしている。よって、$n \geqq 4$ に対して

$$ a_n=a_{n-1}+a_{n-2}+a_{n-3}

$$

が成り立つ。

これを用いて、まず $a_4,a_5$ を求める。

$$ a_4=a_3+a_2+a_1=4+2+1=7

$$

$$ a_5=a_4+a_3+a_2=7+4+2=13

$$

次に、問題の形に合わせて $a_n,a_{n+1},a_{n+2},a_{n+3}$ の間の関係式を書く。上の漸化式で $n$ を $n+3$ に置き換えると、$n \geqq 1$ に対して

$$ a_{n+3}=a_{n+2}+a_{n+1}+a_n

$$

である。

最後に $a_{10}$ を順に求める。

$$ \begin{aligned} a_6&=a_5+a_4+a_3=13+7+4=24,\\ a_7&=a_6+a_5+a_4=24+13+7=44,\\ a_8&=a_7+a_6+a_5=44+24+13=81,\\ a_9&=a_8+a_7+a_6=81+44+24=149,\\ a_{10}&=a_9+a_8+a_7=149+81+44=274. \end{aligned}

$$

解説

この問題では、「最初の1歩」ではなく「最後の1歩」に注目すると、重複なく場合分けできる。最後に上る段数は $1,2,3$ のいずれかであり、それぞれ直前の位置が $n-1,n-2,n-3$ 段目に対応する。

そのため、登り方の総数は直前の3つの段までの登り方の和になる。これは典型的な漸化式の作り方であり、階段を1段または2段ずつ上る問題の拡張である。

答え

**(1)**

$$ a_4=7,\qquad a_5=13

$$

**(2)**

$$ a_{n+3}=a_{n+2}+a_{n+1}+a_n \qquad (n\geqq 1)

$$

**(3)**

$$ a_{10}=274

$$