Deriving the recurrence for the number of strings of length n?

Question

(a) 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$. You need to provide a complete justification for this recurrence. (But you do not need to solve it.)

Ok so I found values for n = 0, 1, 2 by hand, and I got $P_0$ = 1, $P_1$ = 5, and $P_2$ = 21. From that I figured the recurrence is $P_n$ = 4$P_{n - 1}$ + 1. I am not sure if the initial values I calculated are correct or if the recurrence is derived is correct either. I am hoping someone here can let me know if I am thinking correctly and point me in the right direction. Thanks!

Answer 1

See if you can fill in the gaps.

A word of the required type of length $n$ must consist of

any one of $3$ vowels, followed by word of the same type with length $n$: there are $3P_{n-1}$ possibilities;

or

any one of $2$ consonants, followed by ... , followed by a word of the same type with length ... : there are ... possibilities.

Therefore, $P_n=\ ...$

Your initial values are correct.