Help with reasoning on how to set up a recurrence relation

Question

I'm working with the following problem:

An alphabet $\Sigma$ consist of the four numeric characters 1, 2, 3, 4, and the seven alphabetic characters a,b, c, d, e, f, g. Find and solve a recurrence relation for the number of words of length n (in $\Sigma$), where there are no consecutive (identical or distinct alphabetic characters.

My problem is how to reason when I'm setting up the recurrence relation. My reasoning goes like this:

If there's a numeric character last, then the character before it can be either an numeric or an alphabetic character which there exist 4+7=11 characters of. So $11a_{n-1}$

If there's a alphabetic character last, then the character before it can only be an numeric character which there exist 4 characters of. So $4a_{n-2}$

Which gives me the recurrence relation: $a_n = 4a_{n-1} + 11a_{n-2}$

But I don't think my reasoning is sound. please help me out

Answer 1

I usually find it less error-prone to break problems like this into cases explicitly.

Let $s_n$ be the number of valid $n-$character strings than end in an alphabetic character, and let $t_n$ be the number of valid $n-$character strings than end in a numeric character, so that $a_n=s_n+t_n$.

We have $$\begin{align} s_n&=7t_{n-1}\\t_n&=4(s_{n-1}+t_{n-1}) \end{align}$$

Substituting the first equation into the second gives $$\frac{s_{n+1}}7=4\left(s_{n-1}+\frac{s_n}7\right)$$ which we can solve in the usual way. Then we can appeal to the first equation again to get $t_n$, and finally $a_n$.

Alternatively, the last equation can be rewritten as $$s_{n+1}=28s_{n-1}+4s_n,$$ and the first equation shows that $t_n$ must satisfy the same recurrence $$t_{n+1}=28t_{n-1}+4t_n.$$ Adding these two gives $$a_{n+1}=28a_{n-1}+4a_n.$$

Answer 2

So I(think I) managed to solve the problem(or maybe modified @saulapatz good answer). anyway, here it is:

So basically you have two scenarios.

1. a numeric character is the last character.
2. an alphabetic character is the last character.

Scenario 1. if a numeric character is to be the last character, then we have 4 different characters to choose from. and the character that comes before said numeric character doesn't matter. and that gives $$4a_{n-1}$$

Scenario 2. if an alphabetic character is to be the last character, then we have 7 different characters to choose from. But then we must have a numeric character before said alphabetic character, which there are 4 to choose from. that gives us $$(7*4)a_{n-2}=28a_{n-2}$$ Summing it up, we get $$a_n = 4a_{n-1} + 28a_{n-2}$$