Express as a recurrence relation the number of ternary strings of length n that contain either 2 consecutive 0's or 2 consecutive 2's.

Question

Express, as a recurrence relation, the number of ternary strings of length n that contain either 2 consecutive 0's or 2 consecutive 2's. Don't forget to include the base case. Can someone help me start this question? Can we say the base case would be length n = 2 i.e (00 , 22) n = 3 i.e (000, 001, 002, 100, 200, 022, 122, 222,220, 221)

Answer 1

I’ll get you started and give you an outline of how to proceed.

Let $a_n$ be the number of ternary strings of length $n$ that contain either two consecutive $0$s or two consecutive $2$s; I’ll call these good strings. Suppose that $\sigma$ is a good string of length $n$; how could it have been built from shorter strings?

• We can take any good string of length $n-1$ and append a $0,1$, or $2$ to make a good string of length $n$; that accounts for $3a_{n-1}$ good strings of length $n$.

Among those are all of the good strings of length $n$ that end in $1$; why? Those also include all of the good strings of length $n$ that end in $0$ or $2$ and whose first $n-1$ symbols form a good string. What good strings of length $n$ are not yet accounted for?

We have not yet accounted for the good strings of length $n$ that end in $0$ or $2$ and whose first $n-1$ symbols do not form a good string.

Suppose that $\sigma$ is a good string of length $n$ that ends in $0$ and whose first $n-1$ symbols form a bad string. Let $\tau$ be the substring consisting of the first $n-1$ symbols. We know that $\tau$ is bad, so it does not contain $00$ or $22$, but we also know that $\sigma$, which is $\tau0$, is good. This means that $\tau$ must end in $0$. Thus, we get one good string like $\sigma$ for each bad string of length $n-1$ ending in $0$.

Similarly, if $\sigma$ is a good string of length $n$ that ends in $2$ and whose first $n-1$ symbols form a bad string, $\sigma$ must result from appending a $2$ to a bad string of length $n-1$ that ends in $2$.

Putting these two pieces together, we see that we get one good string of length $n$ that ends in $0$ or $2$ and whose first $n-1$ symbols do not form a good string for each bad string of length $n-1$ that does not end in $1$. How many such bad strings are there?

There are $3^{n-1}-a_{n-1}$ bad strings of length $n-1$ altogether. The ones that end in $1$ are all obtained by appending a $1$ to a bad string of length $n-2$. There are $3^{n-2}-a_{n-2}$ bad strings of length $n-2$, so there are $3^{n-2}-a_{n-2}$ bad strings of length $n-1$ that end in $1$, and therefore

$$\left(3^{n-1}-a_{n-1}\right)-\left(3^{n-2}-a_{n-2}\right)$$

bad strings of length $n-1$ that do not end in $1$.

I’ll leave it to you to simplify this and combine it with the first step to get a recurrence for $a_n$ in terms of $a_{n-1}$, $a_{n-2}$, and some function of $n$. It will be a second-order recurrence, so the base cases will be the values of $a_0$ and $a_1$.