6京都大学 2005年 数学 第6問解答・解説

条件を満たす塗り方を $a_n$ 通りとする。先頭が赤なら残りは $a_{n-1}$ 通り。先頭が青または黄なら2通りの後、2両目は赤に固定され、残りは $a_{n-2}$ 通りだから $$a_n=a_{n-1}+2a_{n-2}\quad(n\ge2),\qquad a_0=1,\ a_1=3.$$ $b_n=(2^{n+2}-(-1)^n)/3$ とおくと $b_0=1,b_1=3$。実際、$n\ge2$ で $$\displaystyle \begin{aligned} b_{n-1}+2b_{n-2} &=\frac{2^{n+1}-(-1)^{n-1}+2\{2^n-(-1)^{n-2}\}}{3}\\ &=\frac{2^{n+2}-(-1)^n}{3}=b_n. \end{aligned}$$ よって漸化式と初期値から帰納法で $a_n=b_n$。