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?
Best Answer
$$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.