Recurrence for the number of ternary strings of length $n$ that contain either two consecutive $0$s or two consecutive $1$s

Question

I attempted this problem and this is what I have so far:

First, I considered the possible "cases".

If the string starts with $00$ or $11$, then the rest can be anything so there are $2\cdot 3^{n-2}$ such strings.

If the string starts with $2$, then there are $n-1$ strings that contain two consecutive $0$s or $1$s.

If the string starts with $22$, then there are $n-2$ strings that contain two consecutive $0$s or $1$s.

I came up with the recurrence relation: $$a_n=a_{n-1}+a_{n-2}+2\cdot 3^{n-1}.$$ However, the solution in my textbook says it is actually $$a_n=2a_{n-1}+a_{n-2}+2\cdot 3^{n-2}.$$ I can't seem to figure out why $a_{n-1}$ is multiplied by two.

Answer 1

We can derive the recurrence relation for $a_n$ as follows:

• 00|11: A string may start with either $00$ or $11$ leaving $\color{blue}{2\cdot 3^{n-2}}$ ways for the remaining substring of length $n-2$.

• 22: A string may start with $22$ leaving $\color{blue}{a_{n-2}}$ ways for the remaining substring of length $n-2$.

In all the other cases the string starts

• 0(1|2): either with $0$ followed by $1$ or $2$

• 1(0|2): or with $1$ followed by $0$ or $2$

• 2(0|1): or with $2$ followed by $0$ or $1$.

In each of these three cases the first character is followed by one of two characters leaving $\color{blue}{2a_{n-1}}$ ways for the remaining substring of length $n-1$.

We conclude a recurrence relation for $a_n$ is \begin{align*} a_n&=2a_{n-1}+a_{n-2}+3\cdot 2^{n-2}\qquad\qquad n\geq 4\\ a_2&=2\\ a_3&=10 \end{align*}

The base cases $a_2=2$ and $a_3=10$ can be manually verified by \begin{align*} &n=2:\qquad 00,11\\ &n=3:\qquad 000,001,002,011,100,110,111,112,200,211 \end{align*}

Answer 2

Your argument is not correct because the case "the string starts with 2" include the case "the string starts with 22".

I think it's easier to consider the "complement" sequence.

Let $A_n$, $B_n$ and $C_n$ be the number of ternary strings of length $n$ that contain no consecutive $0$s and no consecutive $1$s, and which start with $0$, $1$, and $2$ respectively. Then $a_n=3^n-(A_n+B_n+C_n)$.

We have the linear recurrences for $n\geq 2$: $$\begin{cases} A_{n}&=B_{n-1}+C_{n-1}\quad &\text{(after a $0$ we can have $1$ or $2$)}\\ B_{n}&=A_{n-1}+C_{n-1}\quad &\text{(after a $1$ we can have $0$ or $2$)}\\ C_{n}&=A_{n-1}+B_{n-1}+C_{n-1}\quad &\text{(after a $2$ we can have $0$, $1$ or $2$)} \end{cases} $$ and it follows that $$ \begin{cases} A_{n}=2A_{n-1}+A_{n-2}\\ B_{n}=2B_{n-1}+B_{n-2}\\ C_{n}=2C_{n-1}+C_{n-2} \end{cases}$$ and by summing them we obtain $$A_{n}+B_{n}+C_{n}= 2(A_{n-1}+B_{n-1}+C_{n-1})+(A_{n-2}+B_{n-2}+C_{n-2}).$$ Hence $$\begin{align} a_{n}&=3^{n}-(A_{n}+B_{n}+C_{n})\\ &= 3^{n}-(2(A_{n-1}+B_{n-1}+C_{n-1})+(A_{n-2}+B_{n-2}+C_{n-2}))\\ &=3^{n}-2(3^{n-1}-a_{n-1})-(3^{n-2}-a_{n-2})\\ &=2a_{n-1}+a_{n-2}+2\cdot 3^{n-2}. \end{align}$$ Since $a_1=0$, and $a_2=2$, it follows that the first terms of the sequence (see OEIS's A193519) are $$0,2,10,40,144,490,1610,5168, 16320, 50930.$$