Recurrence for number of strings of length n without consecutive vowels

Question

Someone asked almost the same question recently, but I'm having a ton of trouble trying to calculate the rest of the problem.

Answer 1

You know the initial values $a_1=5$ and $b_1=21$. Let's write the given data in the form of vectors and matrices. You know that $\begin{pmatrix}a_{n+1}\\b_{n+1}\end{pmatrix}=\begin{pmatrix}0 & 5\\21 & 21\end{pmatrix} \begin{pmatrix}a_{n}\\b_{n}\end{pmatrix}$. Therefore, you need to calculate $\begin{pmatrix}a_{n}\\b_{n}\end{pmatrix}=A^{n-1} \begin{pmatrix}5\\21\end{pmatrix}$ where $A=\begin{pmatrix}0 & 5\\21 & 21\end{pmatrix}$. Do you know how to calculate $A^{n-1}$ efficiently?

Answer 2

Let's call the number of strings of length $n$ without consecutive vowels $a_n$. We have $a_0 = 1$, $a_1 = 26$, and so on.

One gets a string without consecutive vowels by taking a string that ends in a vowel and adding any non-vowel, or one that ends in non-vowel and adding a vowel or a non-vowel. OK, distinguish those cases: call those that end in non-vowel $u_n$, those that end in vowel $v_n$. Then $a_n = u_n + v_n$, and:

• Make one ending in non-vowel: $u_{n + 1} = 21 (u_n + v_n)$
• Make one ending in a vowel: $v_{n + 1} = 5 u_n$

It is easier to solve directly from here. Define generating functions $A(z) = \sum_{n \ge 0} a_n z^n$, and similarly $U(z)$ and $V(z)$. Multiply the recurrences by $z^n$ and sum over $n \ge 0$, recognize the resulting sums: \begin{align} \frac{U(z) - u_0}{z} &= 21 U(z) + 21 V(z) \\ \frac{V(z) - v_0}{z} &= 5 U(z) \\ A(z) &= U(z) + V(z) \end{align} With $u_1 = 0$, $v_0 = 0$, one gets: \begin{align} U(z) &= \frac{21 z}{1 - 21 z + 105 z^2} \\ V(z) &= \frac{1 - 21 z}{1 - 21 z + 105 z^2} \\ A(z) &= \frac{1}{1 - 21 z + 105 z^2} \end{align} Doing the above backwards you get that: $$ a_{n + 2} = 21 a_{n + 1} - 105 a_n $$ Add the initial values $a_0 = 1, a_1 = 26$.