階段の昇り方の数列(2021年浜松医科大学前期数学第3問)

階段の登り方に関する数列は大学入試でしばしば出題され、今年は浜松医科大で出題されたようです。フィボナッチ数列との関連も含めてよくさらっておきたい問題です。


 

階段を一度に1段登る、または1段飛ばして登る登り方をするとき、$n$段目までの登り方の総数を$a_n$とする。例えば、$a_1=1$、$a_2=2$、$a_3=3$ である。以下の問いに答えよ。

(1)$n$を3以上の整数とする。$n-1$段を踏む$n$段目までの登り方の総数を$b_n$、$n-1$段目を踏まない段目までの登り方の総数を$c_n$とする。$b_n$、$c_n$を$a_{1}$、$a_{2}$、$\cdots$、$a_{n-1}$を用いて表せ。

(2)極限値$\displaystyle \lim _{n \to \infty} \dfrac{a_{n+1}}{a_{n}}$が存在することを認めて、この極限値を求めよ。

(3)$n$を$2$以上の整数とするとき、等式$$a_{2 n}=a_{n}^{2}+a_{n-1}^{2}$$が成立することを示せ。

(2021年浜松医科大学 前期第3問)

 

 考え方

階段の登り方の総数の求め方は漸化式を使って求めるのが最もシンプルです。本問では(1)で丁寧に誘導されていますが、階段の登り方が「フィボナッチ数列」に関連していることは知っておきたい重要な事実です。

$n$番目の状態に達するまでに1段階前と2段階前の状況が影響するようなケースではしばしばフィボナッチ数列が登場します。本問の問題設定では、1段登る方法と1段飛ばしで登る方法があるので、$n-1$ 段目から$n$段目、$n-2$ 段目から$n$段目、という2パターンの到達のしかたが考えられます。$n-1$ 段目までの登り方は$a_{n-1}$通り、$n-2$ 段目までの登り方は$a_{n-2}$通りなので、結局$$a_{n}=a_{n-1}+a_{n-2}$$という漸化式が成り立ちます。これを丁寧に求めなさい、と言っているのが(1)です。

(2)を解く上でのポイントは、数列$\{a_{n}\}$の一般項を求める必要は全く無いということです。極限値が存在することを認めてこれを$L$と置けば、$L$に関する二次方程式が得られます。これを解けば一般項を経由せずに極限値が求められます。一般項を求めるのもそこまで困難ではないですが、比較的手間が掛かるのでお勧めできません。

(3)はフィボナッチ数列の有名な性質の一つです。漸化式をゴリゴリ計算して求めるか、登り方の総数を場合分けして求めることになります。個人的にはフィボナッチ数列の「加法定理」から導出するのが好きですが、ここでは組み合わせ論的に求めてみます。


解答例

 

(1)

$n$段目に到達する直前に $n-1$ 段目にいるとき、そこまでの階段の登り方は$a_{n-1}$通りであり、$n-1$ 段目から$n$段目への登り方は1通りしかないから、$$\color{red}{b_{n}=a_{n-1}}$$である。

 

また、$n$段目に到達するまでに $n-1$ 段目を踏まないとき、階段を一度に1段登る、または1段飛ばして登ることしかできないから、$n$段目に到達する直前は必ず $n-2$ 段目にいる。そこまでの階段の登り方は$a_{n-2}$通りであり、$n-2$ 段目から $n-1$ 段目を踏まないように$n$段目へ登る方法は1通りしかないから、$$\color{red}{c_{n}=a_{n-2}}$$である。

 

 

(2)

$a_{n}=b_{n}+c_{n}$ だから(1)より、$n \geqq 3$ のとき$$a_{n}=a_{n-1}+a_{n-2} \quad \cdots (*)$$が成り立つ。

 

ここで、$\displaystyle \lim _{n \rightarrow \infty} \dfrac{a_{n+1}}{a_{n}}=L$($L$ は正の定数)とおくと、$$\begin{aligned}
L &=\lim _{n \rightarrow \infty} \frac{a_{n+1}}{a_{n}} \\
&=\lim _{n \rightarrow \infty} \frac{a_{n}+a_{n-1}}{a_{n}} \quad (\because (*))\\
&=\lim _{n \rightarrow \infty}\left(1+\frac{a_{n-1}}{a_{n}}\right) \\
&=1+\frac{1}{L} \quad \left(\because \displaystyle \lim _{n \rightarrow \infty} \dfrac{a_{n}}{a_{n-1}}=L\right)
\end{aligned}$$より、$$L^2-L-1=0$$ $$\therefore L=\dfrac{1+\sqrt{5}}{2} \quad (\because L>0)$$を得る。よって求める極限値は$$\color{red}{\dfrac{1+\sqrt{5}}{2}}$$である。

 

 

(3)

$n \geqq 2$ のとき、$2n$段目までの登り方について、$n$段目を踏むかどうかで場合を分けて考える。

 

$n$段目を踏むような登り方のとき、$n$段目までの登り方は$a_n$通りであり、$n$段目から$2n$段目までの登り方は$n$段目までの登り方の総数に等しく$a_n$通りとなる。よって$2n$段目までの登り方のうち、$n$段目を踏むような登り方は$a_n^2$通りである。

 

一方、$2n$段目までの登り方のうち、$n$段目を踏まない登り方は、$n-1$ 段目までの登り方が$a_{n-1}$通りであり、$n-1$ 段目から $n+1$ 段目への登り方は1通り、$n+1$ 段目から$2n$段目までの登り方は $n-1$ 段目までの登り方の総数に等しく$a_{n-1}$通りとなる。

 

$2n$段目までの登り方は、$n$段目を踏む登り方と、$n$段目を踏まない登り方の2パターンしかないから、以上ですべての場合を尽くしている。

 

よって、$n \geqq 2$ において、$$\begin{aligned}
a_{2 n} &=a_{n} \cdot a_{n}+a_{n-1} \cdot 1 \cdot a_{n-1} \\
&=a_{n}^{2}+a_{n-1}^{2}
\end{aligned}$$が成立することが示された。

 


 

階段を登る方法の総数はフィボナッチ数列と大いに関係があります。状態$C_n$に達するまでに1歩手前と2歩手前の状況が影響するようなケースではしばしばフィボナッチ数列が登場します。明らかにフィボナッチ数列が登場する問題もあれば、実はフィボナッチ数列が隠れていたというタイプの問題もあり、フィボナッチ数列は数学の色々な所に顔を出します。

(3)について、少し補足しておきます。

フィボナッチ数列$\{F_n\}$について、$m>1 \,(\in \mathbb{N})$ で$$G_{n+m}=F_{m}G_{n+1}+F_{m-1}G_{n}$$という関係式が成り立ちます。ここで数列$\{G_n\}$は$$G_{n+2}=G_{n+1}+G_{n}$$という漸化式で与えられる一般の数列(初項は任意の整数)を表しています。

これは俗に「フィボナッチ数の加法定理」などと呼ばれる公式で、ここから実に多くの興味深い性質を導くことができます。この「加法定理」は$m$に関する数学的帰納法によって容易に示すことができます。

本問の設定では $a_n=F_{n+1}$ なので、上記の加法定理で$G_n$を$a_n$、$F_{n}$を$a_{n-1}$と置いて $m=n$ を代入することにより、所望の関係式が得られます。なお、(2)で一般項を求めてしまっているのであれば(3)は右辺を整理することで求められます。


かつて、似た趣向の問題が京都大学2007年の前期理系大問1問2に出題されています。問題文は以下のようなものでした。

1歩で1段または2段のいずれかで階段を昇るとき、1歩で2段昇ることは連続しないものとする。15段の階段を昇る昇り方は何通りあるか。

この場合は「1歩で2段昇ることは連続しない」という制約によって設定が少しややこしくなっています。

» 答え

このような昇り方は$277$通りです。これは初項が $a_{1}=1$、$a_{2}=2$、$a_{3}=3$ で $a_{n}=a_{n-1}+a_{n-3}$ という漸化式によって定まる数列です。

» 閉じる

フィボナッチ数列ではないですが、1995年の東京大学前期理系第3問で漸化式の立て方について参考になる問題が出題されています。気になる方は探してみて下さい。

“階段の昇り方の数列(2021年浜松医科大学前期数学第3問)” への1件の返信

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です