Create a recurrence relation to determine the number of ternary strings of length n with consecutive 0's or consecutive 1's

Question

The question asks to create a recurrence relation to determine the number of ternary strings of length n with consecutive 0's or consecutive 1's

I came up with the formula: $a_n = 2a_{n-1}+a_{n-2}+2(3^{n-2})$ with the initial conditions $a_0 = 0$ and $a_1 = 0$

I came up with this formula by just looking at the number of strings that satisfied the question for: $a_0, a_1, a_2$ and $a_3$ and my formula gave the correct answer at each step.

My question is: is this an accurate recurrence relation to determine length n ternary strings with consecutive 0's or consecutive 1's, and if so is there a more mathematical approach to this question?

Thanks

Answer 1

Here’s one approach. Call a ternary sequence good if it contains at least one of the substrings $00$ and $11$ and bad otherwise. Let $b_n$ be the number of bad strings of length $n$; clearly $b_n=3^n-a_n$. Let

• $c_n$ be the number of bad strings of length $n$ ending in $0$,
• $d_n$ the number of bad strings of length $n$ ending in $1$, and
• $e_n$ the number of bad strings of length $n$ ending in $2$;

clearly $b_n=c_n+d_n+e_n$. It’s straightforward to find the following recurrences:

$$\begin{align*} c_n&=d_{n-1}+e_{n-1}=b_{n-1}-c_{n-1}\\ d_n&=c_{n-1}+e_{n-1}=b_{n-1}-d_{n-1}\\ e_n&=b_{n-1}\;. \end{align*}$$

To get a bad string of length $n$ ending in $0$, for instance, you must start with a bad string of length $n-1$ ending in either $1$ or $2$ and tack on a $0$. To get a bad string of length $n$ ending in $2$, you can start with any bad string of length $n-1$ and tack on a $2$.

Adding these three recurrences, we see that

$$\begin{align*} b_n&=3b_{n-1}-c_{n-1}-d_{n-1}\\ &=3b_{n-1}-b_{n-1}+e_{n-1}\\ &=2b_{n-1}+e_{n-1}\\ &=2b_{n-1}+b_{n-2}\;. \end{align*}$$

Now rewrite this recurrence in terms of the the $a_k$s and solve for $a_n$:

$$\begin{align*} 3^n-a_n&=2(3^{n-1}-a_{n-1}+3^{n-2}-a_{n-2}\\ &=2\cdot3^{n-1}+3^{n-2}-2a_{n-1}-a_{n-2}\;, \end{align*}$$

so

$$\begin{align*} a_n&=2a_{n-1}+a_{n-2}+3^n-2\cdot3^{n-1}-3^{n-2}\\ &=2a_{n-1}+a_{n-2}+3^{n-1}-3^{n-2}\\ &=2a_{n-1}+a_{n-2}+2\cdot3^{n-2}\;. \end{align*}$$

The point here is that it’s easier to see the recurrences for $c_n,d_n$, and $b_n$ than to see that for $a_n$ or $b_n$ directly, and it turns out not to be too hard to combine them to get what we want.