Find recurrence relation for strings of length n over {A,B,C}(none of the strings should have consecutive As)

Question

Assume that an is number of strings of length n over A B C and none of strings have consecutive As

I have no idea how to find a relation for this

Answer 1

For a recurrence relation, define $u_n$ to be the number of strings of length $n$ with letters $A,B,C$ such that there are no consecutive $A$s, and additionally, the string must end in $A$. Define $v_n$ to be the number of strings of length $n$ with letters $A,B,C$ such that there are no consecutive $A$s, and additionally, the string must NOT end in $A$. Hence, we are to find $u_n+v_n$. We provide a recursive relation:

To find $u_{n+1}$, we know that the last letter has to be $A$, and the first $n$ letters have to be forming a string of $A,B,C$ which does not end in $A$, and has no consecutive $A$s. Hence, $u_{n+1}=v_n$.

Next, to find $v_{n+1}$, we know that the first $n$ letters give us $u_n+v_n$ choices and the last letter can either be $B$ or $C$, giving us $2$ choices. Hence, $v_{n+1}=2(u_n+v_n)$.

Now, we can substitute $u_n=v_{n-1}$ in the recurrence for $v_{n+1}$ to yield $v_{n+1}=2(v_n+v_{n-1})$. After solving this recurrence, we can conclude that the answer is $u_n+v_n=v_n+v_{n-1}$.

This recurrence can be solved using the standard technique. The quadratic $x^2=2x+2$ has roots: $$\frac{2 \pm \sqrt{(2^2+4 \cdot 2 \cdot 1)}}{2}=1 \pm \sqrt{3}$$ So, we can write $v_n=P(1+\sqrt{3})^n+Q(1-\sqrt{3})^n$. This has to hold good for $n=1,2$. Since $v_1=2$ amd $v_2=6$, we have: $$\begin{cases} (P+Q)+\sqrt{3}(P-Q)=2 \\ 4(P+Q)+2\sqrt{3}(P-Q) = 6 \end{cases} \implies (P,Q)=\bigg(\frac{1+\sqrt{3}}{2},\frac{1-\sqrt{3}}{2} \bigg)$$ Hence, $v_n=\frac{1}{2}((1+\sqrt{3})^{n+1}+(1-\sqrt{3})^{n+1})$, and thus: $$v_{n+1}+v_n=\frac{1}{2}((1+\sqrt{3})^{n+1}+(1-\sqrt{3})^{n+1})+\frac{1}{2}((1+\sqrt{3})^{n}+(1-\sqrt{3})^{n})$$