I had a particular question about a recurrence relation:
Find a recurrence relation for the number of $n$-letter sequences using the letters $A, B, C$ such that any $A$ not in the last position of the sequence is always followed by a $B$.
This was my guess, would someone be able to check/correct my answer:
If we think about an $n$-letter sequence, then we know it terminates. Therefore, to find the answer to this question we can think about the last one or two letters. For the last letter, it can either be an $A$, $B$, or $C$. Therefore we have $3a_{n-1}$ possibilities for the rest of the $n$ letters. We can think of it like if we have n letters and choose one to be the last letter, then we have $n-1$ letters left. Then we also have to consider the $A$ that has a $B$ followed after it. Thus, we have $a_{n-2}$ possibilities for the other $n$ letters. In other words, if we have an $n$-letter sequence, and we have both an $A$ and a $B$, then we have $n-2$ letters left. So all in all, the recurrence relation would be
$$
a_n = a_{n-2} + 3a_{n-1}.
$$
Is my answer and explanation correct? Thank you very much in advanced for your help, I really appreciate it!
P.S. I apologize for any formatting issues! Let me know if you have any questions or concerns!
Best Answer
If $a_n$ is the number of possibilities of length $n$ and $A_n$ is the number of those which end with A then you have: $$a_n=3a_{n-1}-2 A_{n-1} \text{ and } A_n=a_{n-1}-A_{n-1}$$ starting with $a(1)=3$, $A(1)=1$.
This is because any of $a_{n-1}- A_{n-1}$ words with $n-1$ letters which do not end in A can be followed by A, B or C, while the $A_{n-1}$ words with $n-1$ letters which do end with A must then be followed by B.
You can show by induction that this is equivalent to $$a_n=2a_{n-1}+a_{n-2} \text{ and } A_n=2A_{n-1}+A_{n-2}$$ starting with $a(1)=3$, $a(2)=7$, $A(1)=1$, $A(2)=2$.