How to find the number of words of length n with a specific rule.

Question

I'm given the following problem:

Consider a language that uses only {1, 2, 3}. The only rule this language has is that a '3' cannot follow a '3'. How many words of length n exist in this language?

From what I gathered, I need to establish a recurrence to solve this problem. I'm not exactly sure how I should go about doing so, however. I tried splitting

$x_n$= $a_n$ + $b_n$

in which $x_n$ is the total number of words of length n that follows the rule and that $a_n$ is the number of words that DO start with '3' while $b_n$ is the number of words that DO NOT start with '3'. This seems to do no good though. Any tips is greatly appreciated.

Answer 1

If you're having trouble defining the recurrence relation due to the number of variables involved, consider that a string can start in one of the four possible ways: $$ 1XXXX ...\\ 2XXXX ...\\ 31XXX ...\\ 32XXX ...\\ $$ If the first digit is a $3$ then the second is not a $3$. However, the digits following a $1$ or a $2$ can be any word in the language. Two of these four cases have an undetermined word of length $n-1$, and the other two have an undetermined word of length $n-2$. This yields the relation $x_n = 2x_{n-1} + 2x_{n-2}$.

Answer 2

if $b_n$ is the number of "good" words that start with a 3 then each of those words has a word of length $n-1$ that does not start with a 3 by removing the first 3 so $b_n=2 \times x_{n-1}$. Also in a similar fashion $a_n= 2 \times x_{n-1}$ .