Thread: Finding a recurrence relation

Define an n-letter word to be a string of n letters, each taken from the 26 letters of the alphabet. Find a recurrence relation for an, n >= 0, where an is the number of n-letter words in which no adjacent letters in the word can both be vowels. (For example, bark is such a 4-letter word, but meow is not.)

Originally Posted by sbankica

Define an n-letter word to be a string of n letters, each taken from the 26 letters of the alphabet. Find a recurrence relation for an, n >= 0, where an is the number of n-letter words in which no adjacent letters in the word can both be vowels. (For example, bark is such a 4-letter word, but meow is not.)

Hint:

Let's say we want to find . For the sake of brevity, let's say a string is "acceptable" if it does not contain two adjacent vowels.

Break the possibilities into two disjoint sets depending on whether the (n+1)-th letter is a vowel. The total number of possibilities is the sum of the sizes of these sets.

If the (n+1)-th letter is a vowel, the preceding n letters can be any acceptable string which does not end in a vowel. If the nth letter is not a vowel, then the preceding n-1 letters can be any acceptable string, which can be done in ways. Then how many choices are there for the nth and (n+1)-th letters?

If the (n+1)-letter is not a vowel, then the preceding n letters can be any acceptable string, which can be done in ways. Then how many choices are there for the (n+1)-th letter?