# Number of words with no adjacent vowels

I am faced with the following problem:

Given $$C = \{B,C,D,F\}$$ and $$V = \{A, E, I, O, U\}$$ find the number of 9-letter words with elements from $$C$$ and $$V$$ such that no two vowels (elements of V) are adjacent.

Following this answer about a very similar question I get that I should express the problem as a double recurrence:

$$a_{n+1} = 5b_n$$, $$a_0 = 1$$

$$b_{n+1} = 4(a_n + b_n)$$, $$a_0 = 1$$

where $$a_n$$ is the number of string starting by a vocal and $$b_n$$ is the number of string starting by a consonant.

Expressing it as a matrix I get $$\begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 5 \\ 4 & 4 \end{pmatrix} \begin{pmatrix} a_n \\ b_n \end{pmatrix}$$

And I get that the eigenvalues of this matrix are $$\{2+\frac{\sqrt{96}}{2}, 2-\frac{\sqrt{96}}{2}\}$$. Is this the correct approach?

I don't really know where to go from here or how to solve the recurrence for any given $$k$$. Thank you in advance

• You made a typo : $\begin{pmatrix} a_{n+1} \\ b_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 5 \\ 4 & 4 \end{pmatrix} \begin{pmatrix} a_n \\ b_n \end{pmatrix}$ – Olivier Roche Sep 11 '19 at 9:21
• @OlivierRoche Yes, fixed, thank you – Zanzag Sep 11 '19 at 9:22

You boil your problem down to a linear recurrence relation, which is nice!

There's a little issue with $$a_0$$ and $$b_0$$, though : how can the empty word start by anything? One should start the recurrence at $$n=1$$, we have $$a_1 = 5$$ and $$b_1 = 4$$.

Call $$A = \begin{pmatrix} 0 & 5 \\ 4 & 4 \end{pmatrix}$$, then $$\begin{pmatrix} a_n \\ b_n \end{pmatrix} = A^{n-1} \begin{pmatrix} 5 \\ 4 \end{pmatrix}$$ The point of computing the eigenvalues is to put $$A$$ in a nicer form so that $$A^n$$ is easy to compute. Since you have two distinct eigenvalues, you can diagonalize $$A$$ which will lead you to a nice expression of $$a_n$$ and $$b_n$$.

Diagonalization of $$A$$ :
Edit : in fact $$96 = 4 \cdot 24$$ and not $$4\cdot 19$$ !

One finds two distinct eigenvalues, $$\lambda_1 = 2 + \sqrt{24}$$ and $$\lambda_2 = 2 - \sqrt{24}$$.
Let $$i=1,2$$, an eigenvector $$v_i$$ corresponding to $$\lambda_i$$ is a nonzero solution to the equation $$(A - \lambda_i \operatorname{Id}) v_i = 0$$ Write $$v_i = \begin{pmatrix} x \\ y \end{pmatrix}$$, we get $$\left\{\begin{matrix} -\lambda_i x + & 5 y = & x \\ 4 x + & (4-\lambda_i)y = & y \end{matrix} \right.$$ The first line implies $$y = \frac{\lambda_i}{5} x$$, after which the second line vanishes. Now chose an arbitrary $$x \neq 0$$, let's take $$x = 5$$ for convenience.

Now $$v_1 = \begin{pmatrix} 5 \\ 2 + \sqrt{24} \end{pmatrix}$$ and $$v_2 = \begin{pmatrix} 5 \\ 2 - \sqrt{24} \end{pmatrix}$$ form a basis of eigenvectors. Take $$P = \begin{pmatrix} 5 & 5 \\ 2 + \sqrt{24} & 2 - \sqrt{24} \end{pmatrix}$$ One has $$P^{-1}AP = \begin{pmatrix} 2 + \sqrt{24} & 0 \\ 0 & 2 - \sqrt{24}\end{pmatrix}$$ Hence, $$A^k = P \begin{pmatrix} (2 + \sqrt{24})^k & 0 \\ 0 & (2 - \sqrt{24})^k\end{pmatrix} P^{-1}$$

• Thank you, I understand it now. – Zanzag Sep 13 '19 at 20:08