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*}