0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Oops, typo. Thank you. $\endgroup$
    – help_me
    Commented Feb 27, 2020 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
    Commented Feb 27, 2020 at 22:12

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .