大学入試で出題される場合の数・確率の問題では，漸化式を利用するものがあります。
問題文からどのように考えて漸化式を立てるのか分からない人も多いのではないでしょうか。
この記事では，問題文から漸化式を立てるときの考え方について説明します。
漸化式を立てることができなければ，そもそも解く漸化式がない状態になるため解答用紙は白紙になります。
そうならないためにも，漸化式を立てることができるようになりましょう。
1995年 東京大
ヒロ
それでは次の入試問題を解いてみよう。
1995年 東京大 2辺の長さが1と2の長方形と1辺の長さが2の正方形の2種類のタイルがある。縦2，横 $n$ の長方形の部屋をこれらのタイルで過不足なく敷き詰めることを考える。その並べ方の総数を $A_n$ で表す。ただし，$n$ は正の整数である。たとえば $A_1=1$, $A_2=3$, $A_3=5$ である。このとき，以下の問いに答えよ。
(1) $n\geqq3$ のとき，$A_n$ を $A_{n-1},~A_{n-2}$ を用いて表せ。
(2) $A_n$ を $n$ で表せ。
(1) $n\geqq3$ のとき，$A_n$ を $A_{n-1},~A_{n-2}$ を用いて表せ。
(2) $A_n$ を $n$ で表せ。
(1)の考え方と解答
ヒロ
問題で3項間漸化式を立てるように誘導されている。
ヒロ
今回は最初に置くタイルに着目して場合分けしよう。
【最初に置くタイルに着目】
最初に置くタイルは長方形か正方形の2通りがある。例えば正方形のタイルを最初に置いた場合は，次の図のようになる。
長方形のタイルを置く場合は，2通りに分かれる。縦に置くと次のようになる。
横に置くと次のようになる。
ここで，縦2，横 $n$ の長方形の部屋にタイルを敷きつめる方法が $A_n$ であることを理解しよう。場合の数 $A_n$ を決めるのは部屋の横の長さ $n$ である。
例えば，縦2，横5の長方形の部屋にタイルを敷きつめる方法は $A_5$ 通りあり，縦2，横 $n-1$ の長方形の部屋にタイルを敷きつめる方法は $A_{n-1}$ 通りあるということ。
正方形のタイルを最初に置いたときは，残りの空いているスペースは縦2，横 $n-2$ の長方形で，ここにタイルを敷きつめる方法を考えると，$A_{n-2}$ 通りある。
長方形のタイルを縦に置いたときは，残りの空いているスペースは縦2，横 $n-1$ の長方形で，ここにタイルを敷きつめる方法を考えると，$A_{n-1}$ 通りある。
長方形のタイルを横に置いたときは，そのタイルの下にも長方形のタイル（図の青いタイル）を横に置くことが確定する。自動的に決まるものについては「何通り」というものを考えないことに注意しよう。結局，残りの空いているスペースは縦2，横 $n-2$ の長方形で，ここにタイルを敷きつめる方法を考えると，$A_{n-2}$ 通りある。
ヒロ
ここまで考えれば(1)の答案を書くことができるね。
【(1)の解答】
最初のタイルの敷き方に着目すると次の(i)～(iii)の3つの場合がある。
(i) $1\times2$ の長方形を縦に置いたとき，残りの縦2，横 $n-1$ の長方形へのタイルの敷き方は，$A_{n-1}$ 通りある。
(ii) $1\times2$ の長方形を横に2つ置いたとき，残りの縦2，横 $n-2$ の長方形へのタイルの敷き方は，$A_{n-2}$ 通りある。
(iii) $2\times2$ の正方形を置いたとき，残りの縦2，横 $n-2$ の長方形へのタイルの敷き方は，$A_{n-2}$ 通りある。
以上より，
最初のタイルの敷き方に着目すると次の(i)～(iii)の3つの場合がある。
(i) $1\times2$ の長方形を縦に置いたとき，残りの縦2，横 $n-1$ の長方形へのタイルの敷き方は，$A_{n-1}$ 通りある。
(ii) $1\times2$ の長方形を横に2つ置いたとき，残りの縦2，横 $n-2$ の長方形へのタイルの敷き方は，$A_{n-2}$ 通りある。
(iii) $2\times2$ の正方形を置いたとき，残りの縦2，横 $n-2$ の長方形へのタイルの敷き方は，$A_{n-2}$ 通りある。
以上より，
\begin{align*}
A_n=A_{n-1}+2A_{n-2}
\end{align*}
A_n=A_{n-1}+2A_{n-2}
\end{align*}
(2)の考え方と解答
(2) $A_n$ を $n$ で表せ。
ヒロ
(1)で立てた漸化式を解くだけだね。
【(2)の解答】
$A_n=A_{n-1}+2A_{n-2}$ より
$A_n=A_{n-1}+2A_{n-2}$ より
\begin{align*}
\begin{cases}
A_n+A_{n-1}=2\left(A_{n-1}+A_{n-2}\right),~A_2+A_1=4 &~\cdots\cdots① \\[4pt]
A_n-2A_{n-1}=-\left(A_{n-1}-2A_{n-2}\right),~A_2-2A_1=1 &~\cdots\cdots②
\end{cases}
\end{align*}
①より\begin{cases}
A_n+A_{n-1}=2\left(A_{n-1}+A_{n-2}\right),~A_2+A_1=4 &~\cdots\cdots① \\[4pt]
A_n-2A_{n-1}=-\left(A_{n-1}-2A_{n-2}\right),~A_2-2A_1=1 &~\cdots\cdots②
\end{cases}
\end{align*}
\begin{align*}
A_n+A_{n-1}&=\left(A_2+A_1\right)\Cdota2^{n-2} \\[4pt]
&=2^n~\cdots\cdots③
\end{align*}
②よりA_n+A_{n-1}&=\left(A_2+A_1\right)\Cdota2^{n-2} \\[4pt]
&=2^n~\cdots\cdots③
\end{align*}
\begin{align*}
A_n-2A_{n-1}&=\left(A_2-2A_1\right)\Cdota(-1)^{n-2} \\[4pt]
&=(-1)^n~\cdots\cdots④
\end{align*}
$\dfrac{③\times2+④}{3}$ より，A_n-2A_{n-1}&=\left(A_2-2A_1\right)\Cdota(-1)^{n-2} \\[4pt]
&=(-1)^n~\cdots\cdots④
\end{align*}
\begin{align*}
A_n=\dfrac{2^{n+1}+(-1)^n}{3}
\end{align*}
A_n=\dfrac{2^{n+1}+(-1)^n}{3}
\end{align*}
ヒロ
隣接三項間漸化式の解法自体を忘れてしまっている人は次の記事で復習しておこう。
まとめ
ヒロ
場合の数・確率を求める問題で漸化式を立てる場合は，最初か最後に着目しよう。
ヒロ
どちらに着目するかは考えやすいと思う方に着目すれば良い。
ヒロ
立てた漸化式を解けないのであれば，完答することができなくなるため，漸化式の解法パターンについても色々知っておく必要がある。
ヒロ
一部の大学では確率漸化式は毎年のように出題されるため，過去問を確認して出題される可能性が高い大学を受験するなら，しっかり対策をしておこう。