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

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.

• Read again what you have written: If the string starts with $2$, why there should be only $n-1$ admissible continuations? – Christian Blatter Nov 19 '17 at 18:43
• Here either stands for $\text{OR}$ or for $\text{XOR}$? (I guess the latter, but I am not that confident in this linguistic nuances). – Jack D'Aurizio Nov 19 '17 at 20:09
• – Robert Z Nov 19 '17 at 20:29
• @penyou: I think you mean $a_{n-1}$ instead of $n-1$ and $a_{n-2}$ instead of $n-2$ in the cases of strings starting with $2$ resp. $22$. – Markus Scheuer Nov 19 '17 at 21:24

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

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

• Could you explain this part in your math: $a_{n+1}=3^{n+1}-(A_{n+1}+B_{n+1}+C_{n+1})= 3^{n+1}-(2(A_{n}+B_{n}+C_{n})+(A_{n-1}+B_{n-1}+C_{n-1}))$ – penyou Nov 19 '17 at 19:38
• Note that $(A_n+B_n+C_n)=3^n-a_n$. Could you please check the answer of your book? It should be $a_n=2a_{n-1}+a_{n-2}+2\cdot 3^{n-2}$. – Robert Z Nov 19 '17 at 19:41
• Answer in textbook: $a_{n} = 2a_{n-1} + a_{n-2} + 2*3^{n-2}$ – penyou Nov 19 '17 at 19:42
• In the question you wrote a different thing... Now it is correct. – Robert Z Nov 19 '17 at 19:47
• By summing the recurrences for $A_n$, $B_n$ and $C_n$, we find that $A_n+B_n+C_n$ satisfies the same recurrence. – Robert Z Nov 19 '17 at 19:56