Alphabet with 6 vowels and 12 consonants, find the amount of words without two consonants in a row.

Question

I just took an exam and as usual with exams, the answers come to you when you're done with the exam and you are sitting in your favourite chair at home. I want to verify my solution as part of my learning process to learn from my mistakes in case I might want to schedule a resit

Consider an alphabet $A$ consisting of $6$ vowels and of $12$ consonants. Valid words consist of no two consonants in a row, so AART is not valid, nor is JUDITH, but JUDIT is fine and so is AAR, as is AIAIAIAIAIAIAIAIAI. $a_n$ denotes the amount of valid words.

---

a) find $a_0$, $a_1$, $a_2$, $a_3$

$a_0=1$, the empty word

$a_1=12+6=18$ (just one letter)

For $a_2$ we considers words like $AT$, $TA$, $IA$(different vowels) and $AA$ (same vowels)

$a_2= 2 \times 6 \cdot 12 + 5 \cdot 6 + 6=144 +30 +6=180$

We expand to three symbols by either adding a vowel to the end of a 2-letter word or by adding a vowel and consonant to a 1-letter word

$a_3=180 \cdot 6 + 6 \cdot 12 \cdot 18 =1080+1296=2376$

---

(b) Find a recurrence relation

(c) solve it

We make a case distinction for a valid word of length $n$, it either ends in a consonant or in a vowel. If it ends in a consonant, we must have obtained it from a valid word of length $n-2$ by placing a vowel followed by a consonant behind it. In all other situations we simply place a vowel behind a word of length $n-1$.

We get for $n\geq 2$: $$ a_n = 6 \cdot a_{n-1} + 6 \cdot 12 \cdot a_{n-2}$$ One can verify that this indeed gives $180$ for $a_2$.

We can solve this recursion via an auxiliary equation of the form:

$$ r^2 = 6r + 6 \cdot 16 $$ $$ r^2 - 6r - 6 \cdot 16 =0$$ Which factorises as:

$$ (r-12)(r+6)=0$$

So we get solutions $a_n = A r_1^n + B r_2^n$:

$$ a_n = A \cdot 12^n + B \cdot (-6) ^n$$

We can now plug in our initial conditions $a_0=1$ and $a_1=18$ $$1=A+B$$ $$ 18= 12A - 6B=18A -6 \implies 18A=24 \implies A=\frac{4}{3}, B=-\frac{1}{3}. $$

We get:

$$ a_n = \frac{4}{3}\cdot 12^n -\frac{1}{3} (- 6)^n$$

I feel that this is probably correct, but I am unsure. Can someone please verify?

Answer 1

$$a_n=6a_{n-1}+6\cdot 12a_{n-2}$$ is correct. From this you get the characteristic polynomial $$ r^2-6r-6\cdot 12 $$ which factors as $$ (r-12)(r+6) $$ Note that the roots of this are $r=12$ and $r=-6$. This is where you went wrong; you had the roots as $r=12$ and $r=6$. The general solution is therefore $$ a_n=A\cdot 12^n+B(-6)^n $$ and you can do the rest.

Answer 2

if there are $a_n$ n-letter words, $c_n$ end in a consonant and $v_n$ end in a vowel

$a_n = c_n + v_n$

To make a n+1 letter word, we take the a_n letter words and tack a letter onto the end.

$a_n = 6c_n + 12 v_n\\ c_{n+1} = 12v_n\\ v_{n+1} = 6 c_n+ 6v_n = 6 a_n$

We probably could do away with $a_n$ and represent just with $c_n, v_n$

$\begin{bmatrix} c_{n+1}\\v_{n+1} \end {bmatrix} = \begin{bmatrix}0&12\\6 & 6\end{bmatrix}\begin{bmatrix} c_{n}\\v_{n} \end {bmatrix}$

$\begin{bmatrix} c_{n+1}\\v_{n+1} \end {bmatrix} = \begin{bmatrix}0&12\\6 & 6\end{bmatrix}^n\begin{bmatrix} c_{1}\\v_{1} \end {bmatrix}$

$\begin{bmatrix} c_{n+1}\\v_{n+1} \end {bmatrix} = \frac 13 \begin{bmatrix}1&-2\\1 & 1\end{bmatrix}\begin{bmatrix}12^n&0\\ 0& -6^n\end{bmatrix}\begin{bmatrix}1&2\\-1 & 1\end{bmatrix}\begin{bmatrix} 12\\6 \end {bmatrix}$

$a_n = \frac {4(12)^n - (-6)^n}{3}$