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

Question

I'm having trouble with this one...I understand others have posted this it seems. However, I don't understand those answers/others some incorrect. I first tried thinking of the different ways this could happen, arranging each case i.e.

case 1: 2 followed by string of n-1 containing 00

case 2: 2 followed by string of n-1 containing 11

case 3: 10 followed by string of n-2 containing 11

case 4: 01 followed by string of n-2 containing 00

case 5: 011 followed by any string of n-3

case 6: 100 followed by any string of n-3

case 6: 00 followed by any string of length n-2

case 7: 11 followed by any string of length n-2

however, not convinced this is correct since im fairly certain there is some overlap/some possiblities im missing.

im assuming it would be a better idea to find ones that DO NOT contain "00" or "11" and subtract that from the total possible 3^n, but im not sure where to start...

Answer 1

HINT: You’re right: it’s simpler to work with the complementary set. Let $a_n$ be the number of ternary strings of length $n$ that do not contain $00$ or $11$; I’ll call such strings good strings. Let $b_n$ be the number of these strings that end in $2$.

Suppose that $\sigma$ is a good string of length $n-1$. If $\sigma$ ends in $2$, we can append any of the three characters $0,1$, and $2$ to it to get a good string of length $n$; that accounts for $3b_{n-1}$ good strings of length $n$.

• If $\sigma$ does not end in $2$, how many different characters can be appended to $\sigma$ to make a good string of length $n$?
• How many good strings of length $n$ does that account for?

Putting the two pieces together will give you an expression for $a_n$ in terms of $a_{n-1}$ and $b_{n-1}$.

• Show that $b_n=a_{n-1}$ and use that to get rid of $b_{n-1}$ in the expression just mentioned. The result will be a recurrence for $a_n$.

To finish off, let $c_n=3^n-a_n$, so that $a_n=3^n-c_n$, and substitute into your recurrence to get a recurrence for $c_n$; that’s what you actually want.

Added: An alternative approach is to notice that each good string $\sigma$ of length $n-1$ can be extended in at least $2$ ways to a good string of length $n$. If $\sigma$ ends in $0$ or $1$, it can be extended in only $2$ ways, with $1$ or $2$ in the first case and with $0$ or $2$ in the second. If $\sigma$ ends in $2$, it can be extended in $3$ ways. Thus, every good string of length $n-1$ contributes $2$ good strings of length $n$, for a total of $2a_{n-1}$ strings, and those that end in $2$ contribute a third one as well. Thus, we need to know (in terms of the $a_k$’s) how many good strings of length $n-1$ end in $2$. Each of those strings is obtained by adding a $2$ to a good string of length $n-2$, so there are how many of them?