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.