Define a recursion that gives the number of sequences that include the numbers $0,1$ that does not contain the sequence $0011$.

Question

Define a recursion that gives the number of sequences that include the numbers $0,1$ that does not contain the sequence $0011$.

The way I thought about it is to start with a all possible beginnings and complete the the beginning to a complete sequence: For example let $a(n)$ be the number of sequences of length $n$, then $a(n+1) =$ possible beginning $1 + a(n) +$ possible beginning $01 + a(n-2) + \ldots$

This method worked on different sequences than $1100$. What I don't understand is why it's not working here.

Thank you.

Answer 1

After a long detour I found the following: $$a_0=1,\quad a_1=2,\quad a_2=4,\quad a_3=8,$$ and then $$a_n=2a_{n-1}-a_{n-4}\qquad(n\geq4)\ .$$ A posteriori this can be justified as follows: You obtain an admissible word of length $n$ by appending a $0$ or a $1$ to an admissible word of length $n-1$. If in this way in the last four steps $0011$ has been appended then you have to cross the resulting word out.