数学B 漸化式の応用 問題 13 解説

方針・初手

最後のタイルの色によって場合を分ける。赤と黄色が隣り合うことだけが禁止条件であり、青はどの色とも隣り合えるので、$n$ 枚目の色ごとの個数 $b_n,c_n,d_n$ を使って漸化式を立てる。

解法1

まず $n=1$ のとき、赤色・黄色・青色のいずれでもよいから

$$ a_1=3 $$

である。

$n=2$ のとき、全体は $3^2=9$ 通りである。このうち、赤色と黄色が隣り合う並べ方は

$$ \text{赤黄},\quad \text{黄赤} $$

の $2$ 通りである。したがって

$$ a_2=9-2=7 $$

である。

次に、$n+1$ 枚目の色で分類する。

$n+1$ 枚目が赤色であるためには、$n$ 枚目が黄色であってはならない。したがって、$n$ 枚目は赤色または青色であるから

$$ b_{n+1}=b_n+d_n $$

である。

同様に、$n+1$ 枚目が黄色であるためには、$n$ 枚目が赤色であってはならない。よって

$$ c_{n+1}=c_n+d_n $$

である。

$n+1$ 枚目が青色である場合、$n$ 枚目の色には制限がない。したがって

$$ d_{n+1}=b_n+c_n+d_n $$

である。

また

$$ a_n=b_n+c_n+d_n $$

なので、

$$ d_{n+1}=a_n $$

でもある。

以上より、求める漸化式は

$$ \begin{aligned} b_{n+1}&=b_n+d_n,\\ c_{n+1}&=c_n+d_n,\\ d_{n+1}&=b_n+c_n+d_n \end{aligned} $$

である。

次に、$a_{n+2}$ を $a_{n+1},a_n$ で表す。

上の式を足し合わせると

$$ \begin{aligned} a_{n+1} &=b_{n+1}+c_{n+1}+d_{n+1}\\ &=(b_n+d_n)+(c_n+d_n)+(b_n+c_n+d_n)\\ &=2b_n+2c_n+3d_n\\ &=2(b_n+c_n+d_n)+d_n\\ &=2a_n+d_n \end{aligned} $$

となる。

これを $n+1$ に置き換えると

$$ a_{n+2}=2a_{n+1}+d_{n+1} $$

である。ここで $d_{n+1}=a_n$ より、

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

を得る。

したがって、$a_n$ は

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

を満たし、初期条件は

$$ a_1=3,\qquad a_2=7 $$

である。

この漸化式の特性方程式は

$$ r^2-2r-1=0 $$

であり、解は

$$ r=1\pm \sqrt{2} $$

である。

よって

$$ a_n=A(1+\sqrt{2})^{n-1}+B(1-\sqrt{2})^{n-1} $$

と表せる。

初期条件 $a_1=3,\ a_2=7$ を代入すると

$$ A+B=3 $$

かつ

$$ A(1+\sqrt{2})+B(1-\sqrt{2})=7 $$

である。

これを解くと

$$ A=\frac{3}{2}+\sqrt{2},\qquad B=\frac{3}{2}-\sqrt{2} $$

となる。

したがって

$$ a_n=\left(\frac{3}{2}+\sqrt{2}\right)(1+\sqrt{2})^{n-1} +\left(\frac{3}{2}-\sqrt{2}\right)(1-\sqrt{2})^{n-1} $$

である。

解説

この問題では、全体の個数 $a_n$ だけを直接追おうとすると、最後が赤色なのか黄色なのか青色なのかが分からず、次のタイルを置くときの制限を判断できない。

そのため、最後の色ごとに $b_n,c_n,d_n$ と分けるのが本質である。特に青色は赤色とも黄色とも隣り合えるので、$d_{n+1}=a_n$ と簡単に表せる。この関係を使うことで、最終的に $a_n$ だけの2項間漸化式

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

に落とし込める。

答え

(1)

$$ a_1=3,\qquad a_2=7 $$

(2)

$$ \begin{aligned} b_{n+1}&=b_n+d_n,\\ c_{n+1}&=c_n+d_n,\\ d_{n+1}&=b_n+c_n+d_n \end{aligned} $$

(3)

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

(4)

$$ a_n=\left(\frac{3}{2}+\sqrt{2}\right)(1+\sqrt{2})^{n-1} +\left(\frac{3}{2}-\sqrt{2}\right)(1-\sqrt{2})^{n-1} $$