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.
Best Answer
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.