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

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

• My idea would be to consider first that you have a ternary string of length $n$. Then you append a number to the end, and ask yourself, how many ways there are to do it so that the result contains "11"? Perhaps you need to divide this into separate cases, depending on the last number of the original string ... – Matti P. Jun 9 '20 at 9:49

## 1 Answer

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