All the binary n-words without the sequence 011

Question

I'm trying to find a recurrence relation for the binary words of length $n$ that don't contain the sequence $011$, my attempt is as follow:

denote $f\left(n\right)$ as the number of such sequences.

The first observation is that there is only one possibility for a sequence of length $n\geq2$ ending in $11$. For $n=2$ it is obvious, and inductively, if the same is true for some $n$, then looking at a sequence of length $n+1$ ending in $11$, so that $011$ won't appear it must end in $111$, but then we have a sequence of length $n$ ending in $11$, which by our hypothesis there is only one possibility.

Now if we have a legal sequence of length $n-1$, we can append $0$ at the end to get a legal sequence of length $n$. If we want to append $1$ there are two possibilities, either we have legal sequences of length $n-2$ and append $01$ at the end, or we want to append $11$, which as we've seen there is only one possibility. This shows us that $$f\left(n\right)=f\left(n-1\right)+f\left(n-2\right)+1$$

Though honestly I don't think my arguments in the second paragraph are correct. Not sure how to justify them anyway..

Answer 1

Your argument is fine. To put it a little more clearly, for $\ n\ge2\ $ the number of legal sequences of length $\ n\ $ is $f(n-1)+f(n-2)+1$ because there are exactly $f(n-1)$ legal sequences of length $n$ ending with $0,\ f(n-2)$ ending with $01,$ and just one ending with $11.$ A legal sequence ending with $11$ must be all $1$'s because, if it had any $0$'s, then the rightmost $0$ would be the start of a $011.$

Answer 2

• Taken two recursive functions $f$ and $g$ defined as.

$f_n=\begin{cases} 0\ + g_{n-1} \\ 1\ + f_{n-1} \\ \end{cases}$

$g_n=\begin{cases} 0 \ \ + g_{n-1} \\ 10+ g_{n-2} \\ \end{cases}$

-With $f_0=f_0=\phi$, the first sequence $f$ guarantees an optional arbitrary stream of $1$s, followed by the second $g$ which guarantees no occurence of two consecutive $1$s after any $0$.