Find a recurrence for the number words of length n in the alphabet {A,C, T,G} without two consecutive A’s. So I know how to solve recurrence relations but I'm having a hard time trying to find $W_{1}$ and $W_{2}$ (for solving the recurrence). I arrived to the conclusion that my initial conditions can be $a_{0}$ = 1, $a_{1}$ = 4 and $a_{2}$ = 15. But now I'm stuck on solving the recurrence. With some tries I obtained $W_{1}$ = $a_{n-2}$ and $W_{2}$ = $a_{n-3}$, but really I do not know if that makes sense. So my recurrence relation will something like $a_{n}$ = $a_{n-2}$ + $a_{n-3}$. I will be grateful if someone can help with this step. Thanks in advance.
 A: If a word begins with $A$, then there are three possibilities for the second letter (namely, $C, T$ or $G$) since it is not possible to have two consecutive $A$s.  Since the second letter is not an $A$, any admissible word of length $n - 2$ can be appended to the end of a word that begins with $AC$, $AG$, or $AT$ to form an admissible word of length $n$.  Hence, there are $3a_{n - 2}$ such words.
If a word does not begin with $A$, then it must begin with one of the three letters $C, T$, or $G$.  Such a word can be extended to a word of length $n$ by appending any admissible word of length $n - 1$ to the end of the words $C$, $T$, or $G$.  Hence, there are $3a_{n - 1}$ such words.
Since each word must either begin or not begin with an $A$,
$$a_n = 3a_{n - 1} + 3a_{n - 2}$$
subject to the initial conditions that $a_0 = 1$ since there is one empty word and $a_1 = 4$ since any word of length $1$ is admissible.  Notice that our recursion gives $a_2 = 3 \cdot 4 + 3 \cdot 1 = 12 + 3 = 15$, as expected.
