Recurrence relation for words length $n$

Question

I need to solve following question:

"An alphabet consists out of 4 letters $a,b,c,d$ and 3 numbers $1,2,3$. Find the recurrence relation for the number of words of length $n$ where no two numbers are allowed to be adjacent."

This is what I came up with:

If the first character of the word is a letter, we have 4 possible choices and leaves us with $n-1$ characters left. If the first character is a number, we know the second one is not allowed to be a number as well, so we're left with 4 choices and $n-2$ left to divide.

Which gives me $a_n = 4 a_{n-1} + 4 a_{n-2}$

Not sure if this gives me the correct answer.

Answer 1

Your reasoning is on the right track, but your recurrence relation does't make sense. As you pointed out, if the first character is a letter ($4$ ways this can happen), then we can have any valid word of length $n-1$ to complete the word. That gives us $4a_{n-1}$ words of this type. Now, if the first character is a number ($3$ ways this can happen,) then the next character must be a letter ($4$ ways this can happen), and the remaining $n-2$ characters can be filled with any valid word of length $n-2$. That gives us $12a_{n-2}$ words of this type. There are no other ways to make a valid word of length $n,$ so $$a_n=4a_{n-1}+12a_{n-2}.$$

Added: Noting that $a_1=7$ and that $a_0=1$ (the "empty word" of $0$ characters) gives us the rest of the story.

Answer 2

A sure win in these situations is to consider separately the number $L_n$ of words of length $n$ ending with a letter and the number $N_n$ of words of length $n$ ending with a number, so that one is after the total number $W_n=L_n+N_n$ of words of length $n$.

Then $L_1=4$, $N_1=3$, and considering the ways to complete words of length $n$ of each type to get words of length $n+1$ of each type, one sees that $L_{n+1}=7L_n+7N_n$ and $N_{n+1}=7L_n+4N_n$.

Can you take on from here?