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

  • $\begingroup$ 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 ... $\endgroup$ – Matti P. Jun 9 '20 at 9:49

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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.