Let $P_n$ be the number of strings of length n formed from letters A, B, C, E, O, that do not contain two consecutive consonants (that is, B or C). For example, AABOCA and BACOOEBO satisfy this condition, while AABCEC does not. Derive a recurrence relation for the numbers $P_n$.
So the recurrence is $P_n = 3P_{n - 1} + 6P_{n - 2}$ but I am having trouble proving it. If anyone can help me with the proof I would really appreciate it!
On
Martin mentioned first three cases, so lets look at other cases. For the last two cases string can start with $B$ or $C$ but then how many choices for the second letter of string?
Here is question to understand your question better:
Does string can have part $BB$ or $CC$ or you mean it cannot have all $BC$, $CB$ and $CC$, $BB$?
if it cannot contain $BB$ and $CC$, then
Take the case when string start with $B$ the second letter can not be $B$ and $C$. So we have 3 choices for the second letter of string. Then the rest will be same when the case $n-2$.
Similar way holds for the string that starts with $C$.
So we have your recurrence.
But as i asked before, if the string can contain $BB$ and $CC$ then
we will have 4 choices for the second letter of string so the recurrence will be changed a little meaning that coefficient of $n-2$ term will be $8$.
Take an acceptable $n$-letter string and consider the cases: $$AXXX\cdots$$ $$BXXX\cdots$$ $$CXXX\cdots$$ $$EXXX\cdots$$ $$OXXX\cdots$$ In the three cases $AXXX\cdots$, $EXXX\cdots$, $OXXX\cdots$ the $XXX\cdots$ part can be any acceptable $n-1$-letter string. Can you continue with the cases $BXXX\cdots$ and $CXXX\cdots$?