18. A positive integer is said to be 'good' if each digit is 1 or 2 and there is neither four consecutive 1 's nor three consecutive 2 's. Let $a_{n}$ denote the number of $n$-digit positive integers that are 'good'. Find the value of $\frac{a_{10}-a_{8}-a_{5}}{a_{7}+a_{6}}$.
(2 marks)
若某正整數的每個數字均為 1 或 2 , 且當中既沒有四個連續的 $\ulcorner 1$ 亦沒有三個連續的 22 , 便稱為 「好數」。設 $a_{n}$ 表示 $n$ 位「好數」的數目。求 $\frac{a_{10}-a_{8}-a_{5}}{a_{7}+a_{6}}$ 的值。
18. 2
18. Let $p_{n}$ be the number of $n$-digit 'good' positive integers ending with 1 and $q_{n}$ be the number of $n$-digit 'good' positive integers ending with 2 . Then $a_{n}=p_{n}+q_{n}$. Furthermore a 'good' positive integer must end with $21,211,2111,12$ or 122 . This leads to the recurrence relations $p_{n}=q_{n-1}+q_{n-2}+q_{n-3}$ as well as $q_{n}=p_{n-1}+p_{n-2}$. It follows that
$$
\begin{array}{l}
p_{n}=\left(q_{n-2}+q_{n-3}\right)+\left(q_{n-3}+q_{n-4}\right)+\left(q_{n-4}+q_{n-5}\right)=q_{n-2}+2 q_{n-3}+2 q_{n-4}+q_{n-5} \\
q_{n}=\left(p_{n-2}+p_{n-3}+p_{n-4}\right)+\left(p_{n-3}+p_{n-4}+p_{n-5}\right)=p_{n-2}+2 p_{n-3}+2 p_{n-4}+p_{n-5}
\end{array}
$$

Adding gives $a_{n}=a_{n-2}+2 a_{n-3}+2 a_{n-4}+a_{n-5}$. In particular $a_{10}=a_{8}+a_{5}+2\left(a_{7}+a_{6}\right)$ and so
$$
\frac{a_{10}-a_{8}-a_{5}}{a_{7}+a_{6}}=2 .
$$