I'm trying to find a recurrence relation for the number of words of length $n$ that do NOT contain two consecutive vowels.

I'm trying to relate the problem to a similar one, of bit strings (Say, a relation for the number of bit strings that do not contain four consecutive 0's), but I'm starting to think I don't understand that either.

My though process:

Assume $a_n $ represents the number of words that do not contain consecutive vowels. If there are 26 letters in the English alphabet and 5 vowels (not including the letter "y"), then there are $26^n$ total words. When researching online, I find that similar problems lead people to using $a_{n-1}$, but I don't understand where that comes from. Can anyone offer me some insight? Thank you.

  • $\begingroup$ Oops, typo. Thank you. $\endgroup$ – help_me Feb 27 '20 at 22:11
  • 3
    $\begingroup$ You could look at this question, which is the same except for the number of characters in each group. $\endgroup$ – Ross Millikan Feb 27 '20 at 22:12

Think as follows: A sequence of length $n$ that doesn't end in a vowel can be followed by a non-vowel or a vowel followed by a non-vowel. This gives a recurrence (How many of those are of length 0? 1?). Solve that one, and consider the case where it ends in vowel.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.