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

Question

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?

Answer 1

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

Answer 2

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