# Find a recurrence relation for the number of ternary strings of length n that contain either two consecutive 0s or two consecutive 1s.

I've been stuck on this one for a little bit now. I've looked at the other similar questions on here, but I don't understand the general process for going about forming a recurrence relation from this. How should I go about looking at this problem?

• Can the strings contain both two consecutive $0$'s and two consecutive $1$'s? Can they contain a run of more than two consecutive? – Marconius Oct 20 '15 at 2:43

Let $b_n$ be the number of $n$-digit ternary strings which begin with $0$ and contain neither $00$ nor $11$. Let $c_n,d_n$ be the same except starting with $1$ or $2$ respectively. Let $$t_n=b_n+c_n+d_n$$ be the total number of $n$-digit ternary strings which contain neither $00$ nor $11$. What you want is $$a_n=3^n-t_n\ .$$ To find a recurrence for $b_n$ observe that an $n$-digit ternary string which begins with $0$ and contains neither $00$ nor $11$ is

• $0$, followed by an $(n-1)$-digit string which begins with $1$ and contains neither $00$ nor $11$; or
• $0$, followed by an $(n-1)$-digit string which begins with $2$ and contains neither $00$ nor $11$.

Therefore $$b_n=c_{n-1}+d_{n-1}\ ;$$ similar arguments give $$c_n=b_{n-1}+d_{n-1}$$ and $$d_n=b_{n-1}+c_{n-1}+d_{n-1}=t_{n-1}\ .$$ Adding all of these gives $$t_n=2t_{n-1}+d_{n-1}$$ and so $$t_n=2t_{n-1}+t_{n-2}\ .$$ Writing in terms of $a_n$, we have $$3^n-a_n=2(3^{n-1}-a_{n-1})+(3^{n-2}-a_{n-2})$$ which simplifies to $$a_n=2a_{n-1}+a_{n-2}+2\times3^{n-2}\ .$$

• This way of arriving at a recurrence relation gave a good insight into it – jblixr Jan 24 '17 at 1:26

Above answer by Mr.David is excellent, I would like to tell how I developed intuition. We can see that we need either $$2$$ consecutive $$0$$'s or $$2$$ consecutive $$1$$'s. So we can place $$2$$ consecutive $$0$$'s at the end so for the rest of the $$n-2$$ positions can have any bit out of $$3$$ hence $$3^{n-2}$$ possibilities and same for $$2$$ consecutive 1's so total of $$2\times3^{n-2}$$.

Now the core thought. We obtained string ending with $$00$$ or $$11$$ but string can end with $$01$$, $$02$$, $$10$$, $$12$$, $$20$$, $$21$$ or $$22$$. So what we can think is that all $$n-1$$ length string must be ending with the $$0$$, $$1$$ or $$2$$. Now for $$n$$'th position we can give $$2$$ choices for each last bit of $$n-1$$ string that is if last bit is $$1$$ then it has $$2$$ choices $$0$$ or $$2$$ (we can not give $$1$$ as a choice because it will create string ending with $$11$$ but we already covered that case). Similarly, $$0$$ will have $$2$$ choices for $$n$$'th position, either $$1$$ or $$2$$, and also $$2$$ will have $$2$$ choices (can be any $$2$$). But we know for $$2$$ all the three i.e. $$0$$, $$1$$ and $$2$$ are valid at $$n$$'th position but we counted only $$2$$ (any $$2$$ of your choice). Lets say you had counted string ending with $$20$$ and $$22$$. The remaining case that string ends with $$21$$ can be added by appending $$2$$ and $$1$$ to the string of length $$n-2$$ containing $$2$$ consecutive $$0$$'s or $$2$$ consecutive $$1$$'s.

So the final intuitive (but right) answer becomes $$a(n) = 2\times3^{n-2} + 2a(n-1) + a(n-2)\text.$$