1
$\begingroup$

How can I find a recurrence relation to calculate the number of strings of $n$ characters (english alphabet, lowercase) that don't have consecutive vowels.

It's clear that for $n = 1$ the result is $26$, but, then what? Just hints.

$\endgroup$
4
$\begingroup$

Call such sequences good. Let $a_n$ be the number of good $n$-sequences that end in a vowel, and $b_n$ the number of good $n$-sequences that end in a consonant. Then $$a_{n+1}=5b_n$$

$$b_{n+1}=21(a_n+b_n).$$

From this one can derive a recurrence relation for the number $x_n$ of $n$-sequences that do not have $2$ consecutive vowels. As per request, we leave the details to you.

$\endgroup$

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.