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

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?

• Your reasoning looks fine to me :-) Jan 31, 2019 at 20:54
• You have a typo; you wrote "$r^2=6r-6\cdot 16=0$", when I think you meant "$r^2-6r-6\cdot 12=0$". Jan 31, 2019 at 21:33
• $a_3=180 \cdot 6 + 6 \cdot 12 \cdot 18 =1080+1296=2376$ Feb 1, 2019 at 1:37

$$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.

• Thanks for checking! :)
– user459879
Feb 1, 2019 at 13:08

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}$$

• This is a nice method that I will try to use myself more often :)
– user459879
Feb 1, 2019 at 13:09