$8 \cdot 95$ Find the number of sequences that satisfy the following conditions: the number of terms is $n$, each term is 0 or 1 or 2, and 0 cannot be the preceding term or the following term of 2.
[Solution] Let the number of sequences ending with 0 be $a_{n}$, those ending with 1 be $b_{n}$, and those ending with 2 be $c_{n}$. Clearly, $a_{1}=b_{1}=c_{1}=1$. It is easy to see that the following recurrence relations hold:
$$
\begin{array}{l}
a_{n+1}=a_{n}+b_{n}, \\
b_{n+1}=a_{n}+b_{n}+c_{n}, \\
c_{n+1}=b_{n}+c_{n} .
\end{array}
$$

Thus, for $n \geqslant 2$, we have
$$
\begin{aligned}
a_{n+1}+b_{n+1}+c_{n+1} & =2 a_{n}+3 b_{n}+2 c_{n} \\
& =2\left(a_{n}+b_{n}+c_{n}\right)+\left(a_{n-1}+b_{n-1}+c_{n-1}\right) .
\end{aligned}
$$

From $a_{1}=b_{1}=c_{1}=1$, we can deduce that
$$
a_{2}=2, b_{2}=3, c_{2}=2 \text {. }
$$

Let the number of sequences be $x_{n}$, then obviously
$$
x_{n}=a_{n}+b_{n}+c_{n} .
$$

From the result of the previous section, we know
$$
x_{1}=3, x_{2}=7, x_{n+1}=2 x_{n}+x_{n-1}, n=2,3,4, \cdots
$$

Therefore,
$$
x_{n}=\frac{1}{2}\left[(1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n+1}\right] .
$$