Finding a recurrence relation for the number of ternary strings of length $n$ containing $11$

Question

Find the recurrence relation for $$a_n = \text{number of ternary strings of length $n$, containing $11$}$$

Some of these strings are: $11$, $112$, $1102$,... .

I'm thinking that is same if the question was for $00$ because I have found many solutions for this one in Google. At least the idea I think it would be the same.

First to take all ternary string $3^n$, I'm stuck here... .

Answer 1

First, let's define $b(n) := 3^n-a(n)$, the number of ternary strings that don't contain the substring $11$, as it is easier to find a recurrence relation for this in the fist place.

Since the empty string and any of the strings of length $1$ do not contain the substring $11$, we find that $b(0)=1$ and $b(1)=3$.

Now, for $n\ge 1$, we try to build a feasible string (not containing $11$) of length $n+1$. Such a string can start with either $0$ or $2$ followed by any feasible string of length $n$, or it can start with $1$ followed by either $0$ or $2$ and then any feasible string of length $n-1$. This leads to the recurence formula $b(n+1)=2\cdot b(n)+2\cdot b(n-1)$.

Now, since $b(n)=3^n-a(n)$ for all $n \ge 0$, we see that $$\begin{align} 3^{n+1}-a(n+1)&=2\cdot(3^n-a(n))+2\cdot(3^{n-1}-a(n-1))\\ \iff a(n+1)-2\cdot a(n)-2\cdot a(n-1)&=3^{n+1}-2\cdot3^n-2\cdot3^{n-1}\\ &=3^{n-1} \end{align}$$

This is a recurrence relation for $n \ge 1$, but it contains the term $3^{n-1}$ which we still can eliminate for $n \ge 2$ in the following way: $$\begin{align} 3^{n-1}&=3\cdot 3^{n-2}\\ \iff a(n+1)-2a(n)-2a(n-1)&=3\cdot(a(n)-2a(n-1)-2a(n-2)) \end{align}$$ Solving this for $a(n+1)$, we find the linear recurrence relation for all $n \ge 2$: $$ a(n+1)=5\cdot a(n)-4\cdot a(n-1)-6\cdot a(n-2) $$ Of course, we have to specify the initial values for the recursion, which are $a(0)=a(1)=0$ and $a(2)=1$.

Added:

Just in case you need an explicit formula: $$ a(n) = 3^n+\frac{2-\sqrt{3}}{2\sqrt{3}}\left(1-\sqrt{3}\right)^n-\frac{2+\sqrt{3}}{2\sqrt{3}}\left(1+\sqrt{3}\right)^n $$