How many words?

Let $X_n$ be the number of valid $n$ -letter words (i.e. with no consecutive $A$ s). Then $X_0 = 1$ and $X_1 = 4$ . Suppose now that $n \ge 2$ . If the first letter of the word is $A$ , then the second letter must be one of $C,G,T$ , and the remaining $n-2$ letters must form a valid word. Thus there are $3X_{n-2}$ valid $n$ -letter words beginning with $A$ . If the first letter of a word is not $A$ , then the remaining $n-1$ letters must form a valid word. Thus there are $3X_{n-1}$ valid $n$ -letter words not beginning with $A$ . Hence $X_n \; =\; 3X_{n-1} + 3X_{n-2} \hspace{2cm} n \ge 2$ From this it is easy to calculate that $X_8 = \boxed{44631}$ .

More generally, expressions of the form $X_n = u^n$ will satisfy the recurrence relation provided that $u^2 - 3u - 3 = 0$ , and so $u = \tfrac12(3 \pm\sqrt{21})$ . Since $X_0=1$ and $X_1=4$ we deduce that $X_n \; = \; \frac{1}{3\sqrt{21}}\left[\left(\frac{3 + \sqrt{21}}{2}\right)^{n+2} - \left(\frac{3-\sqrt{21}}{2}\right)^{n+2}\right] \hspace{2cm} n \ge 0$