# Thread:

1. ## 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.)

2. 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 $a_{n+1}$. 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 $a_{n-1}$ 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 $a_n$ ways. Then how many choices are there for the (n+1)-th letter?
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 3, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8746001124382019, "perplexity_flag": "head"}