高校生のみなさんこんにちは。
明野の塾、進学予備校ウインロード大分明野校の首藤です。
今回は場合の数と漸化式を組み合わせた問題です。ちょっと解いてみてください。
問題
階段を上がるとき、一度に上がることができる段数は１段または２段のみであるとする。
nを正の整数とするとき、ちょうどn段上る方法は全部で何通りあるかを答えなさい。
(2020大分大学医学部)
解答は以下の通り。
\[n段上る方法を a_{n}通りとするとn段に到達するにはn-1段目から１段上がるか\]
\[n-2段目から２段上がるかのいずれかである。n-1段目まではa_{n-1}通りで\]
\[n-2段目まではa_{n-2}通りなので、a_{n}=a_{n-1} ＋ a_{n-2}が成り立つ。\]
\[つまりa_{n+2}=a_{n+1} ＋ a_{n}という漸化式ができる\]
ここが大切なところで、n段目が何通りなのかを直接考えるのではなく、その前後との関係に着目する。場合の数、確率ではよく出る問題です。
\[隣接３項間漸化式なので、特性方程式x^2-x-1=0を解いて、\]
\[次のように式変形し\]
\[a_{n+2}-\left(\frac{1+\sqrt{5}}{2}\right)a_{n+1}=\left(\frac{1-\sqrt{5}}{2}\right)\left\{a_{n+1}-\left(\frac{1+\sqrt{5}}{2}\right)a_{n}\right\}−①
\]
\[a_{n+2}-\left(\frac{1-\sqrt{5}}{2}\right)a_{n+1}=\left(\frac{1+\sqrt{5}}{2}\right)\left\{a_{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)a_{n}\right\}−②
\]
\[a_{1}=1とa_{2}=2で\]①より
\[a_{n+1}-\left(\frac{1+\sqrt{5}}{2}\right)a_{n}=\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\left\{a_{2}-\left(\frac{1+\sqrt{5}}{2}\right)a_{1}\right\}
\]
\[a_{n+1}-\left(\frac{1+\sqrt{5}}{2}\right)a_{n}=\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\left\{２-\left(\frac{1+\sqrt{5}}{2}\right)\right\}
\]
\[a_{n+1}-\left(\frac{1+\sqrt{5}}{2}\right)a_{n}=\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\left(\frac{3-\sqrt{5}}{2}\right)
\]
\[\left(\frac{1-\sqrt{5}}{2}\right)^{2}=\frac{6-2\sqrt{5}}{4}=\frac{3-\sqrt{5}}{2}であるので\]
\[a_{n+1}-\left(\frac{1+\sqrt{5}}{2}\right)a_{n}=\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}—①
\]
\[同様に②よりa_{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)a_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}—②\]
\[②ー①より\sqrt{5}a_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\]
\[a_{n}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right]\]