The Number of 3-letter {X,Y,Z} words with no Adjacent Z's. Let $a_n$ denote the number of character strings from the alphabet S = {X, Y, Z} of length n with no two adjacent letters being Z's. Find a recurrence relation model of the number of words.
HINT
(Sorry the hidden feature is not working.)

! To start n=0 is 1 due to the empty set.
! n=1 is 4  three valid solutions {X}, {Y}, {Z} and the previous empty set.
! n=2 is 12 8 valid solutions {XX,XY,XZ}; {YX,YY,YZ}; {XZ,XY,ZZ} and the previous n=1.

 A: Try a recursive relation in two variables. Let $a_n$ denote the number of strings of length $n$ that begin with $Z$, and $b_n$ denote the number of strings of length $n$ that begin with $X$ or $Y$.
We then have:
$$a_{n+1} = b_{n}$$
$$b_{n+1} = 2(a_n + b_n)$$
where the first relation is obtained because for each string of length $n+1$ that begins with $Z$, we may adjoin a string that begins with $X$ or $Y$ to it, and for each string of length $n+1$ that begins with $X$ or $Y$, we may adjoin any string of length $n$ to it.
EDIT: Solving the recurrence.
We consider the two relations above in matrix form:
$$\begin{bmatrix} a_{n+1}\\b_{n+1}\end{bmatrix} = \begin{bmatrix} 0 & 1\\2 & 2\end{bmatrix}\begin{bmatrix} a_{n}\\b_{n}\end{bmatrix}$$
So the characteristic equation of the coefficient matrix, as well as the sequences $a_{n}$ and $b_{n}$ is
$$\begin{vmatrix} -\lambda & 1 \\ 2 & 2-\lambda \end{vmatrix} = \lambda^2 - 2\lambda - 2 = 0,$$
which gives roots $\lambda_{1} = 1 + \sqrt{3}$ and $\lambda_{2} = 1 - \sqrt{3}$.
Solving the general formulae for $a_{n}$ and $b_{n}$ by substituting the first two values yields
$$a_n = \frac{1}{2\sqrt{3}}( (1+\sqrt{3})^n - (1-\sqrt{3})^n)$$
$$b_n = \frac{1}{6}((3+\sqrt{3})(1+\sqrt{3})^n + (3-\sqrt{3})(1-\sqrt{3})^n)$$
Summing the two yields a formula for strings of length $n$. If you wish to compute the number of strings of length $n$ or less, just substitute the two formulae above into
$$c_n = \sum_{k=1}^{n}(a_k + b_k)$$
I'm sure you can get a cleaner answer, but this is all I have to say...
