Recurrence relation to find ternary strings of length $n$ that do not contain $3$ consecutive $0$'s or $2$ consecutive $1$'s

Question

OK my idea is that the total number of possible ternary strings of length $n$ is $3^n$, of which I must subtract the strings containing $000$s plus the strings containing $11$s, excluding the number of duplicates (strings containing both $000$s and $11$s).

Sequence for strings containing 000s: $$f(n)=3\times f(n-1)+2\times(3^{n-4}-f(n-4))$$ Sequence for strings containing 11s: $$f(n)=3\times f(n-1)+2\times(3^{n-3}-f(n-3))$$

Now for the strings containing both sequences: For $n=5$ we get $2$ ($00011$ and $11000$).

For $n=6$ we get $12$ and for $n=7$ we get $73$ (just by producing the permutations).

For $n>5$, I understand we must consider two different cases, the first (or last) $5$ digits forming a "good" sequence (i.e. containing both sequences), in which case, the remaining $n-5$ can be anything (thus giving us $3^{n-5}$ more combinations, or $f(n-1)$ being "bad".

In this case, how do we distinct whether it contains only $000$s or $11$s or none of the two?

In short, how do we find the recurrence relation for the strings to contain both?

Answer 1

Let $f(n)$ be the number of strings starting with 0, $g(n)$ the number starting with 1, $h(n)$ the number starting with 2.

We have $f(n+1)=g(n)+h(n)+g(n-1)+h(n-1)$ (nos. starting 01,02,001,002 resp).

$g(n+1)=f(n)+h(n)$ (nos. starting 10,12 resp).

$h(n+1)=f(n)+g(n)+h(n)$ (nos. starting 20, 21, 22 resp).

Subs 2nd equ in other two we get:

$f(n+1)=f(n-1)+h(n-1)+h(n)+f(n-2)+h(n-2)+h(n-1)=f(n-1)+f(n-2)+h(n)+2h(n-1)+h(n-2)$ (*) and

$h(n+1)=f(n)+f(n-1)+h(n-1)+h(n)$ and hence $h(n)=f(n-1)+f(n-2)+h(n-1)+h(n-2)$ (**)

Subs (**) in (*) we get: $f(n+1)=2h(n)+h(n-1)$. Subs that in the equ for $h(n+1)$ gives $h(n+1)=2h(n-1)+h(n-2)+2h(n-2)+h(n-3)+h(n-1)+h(n)$ or

$h(n+1)=h(n)+3h(n-1)+3h(n-2)+h(n-3)$.

Note that $h(n+1)$ is also the total number of strings of length $n$ - because it is $f(n)+g(n)+h(n)$.

So writing $t(n)$ for the total number of strings of length $n$ we have:

$t(n+1)=t(n)+3t(n-1)+3t(n-2)+t(n-3)$. It is easy to list the possible strings for small $n$ to get $t(1)=3, t(2)=8, t(3)=21, t(4)=55$.