Find a recurrence relation for the number of bit strings of length n that do not contain "0011" So this is what I thought:
i) start with 1: $f(n-1)$
ii)start with 01: $f(n-2)$
iii) start with 000 : $f(n-3)$
iv) start with 0010: $f(n-4)$
Though I was told it's not true.
I would like to know what did I did wrong, and what's the solution.
Thanks
 A: The most straightforward way to start solving a problem like this is to begin by defining a recurrence relation with four variables: $$f_\varnothing(n), f_1(n), f_{11}(n), f_{011}(n)$$  where the subscript represents the longest initial part of the string that matches the end of $0011$. For example, the string $110110$ would be counted by $f_{11}(6)$. We will then have $f(n) = f_\varnothing(n) + f_1(n) + f_{11}(n) + f_{011}(n)$.
We can write recurrence relations for these in terms of each other:
\begin{align}
  f_\varnothing(n+1) &= f_\varnothing(n) + f_1(n) \\
  f_1(n+1) &= f_\varnothing(n) + f_{011}(n) \\
  f_{11}(n+1) &= f_1(n) + f_{11}(n) \\
  f_{011}(n+1) &= f_{11}(n)
\end{align}
Here's the idea for how to get this expression: if we have a string counted by $f_{11}(n)$, for example, we can either 


*

*add a $0$ to the start, and get a string counted by $f_{011}(n+1)$, or 

*add a $1$ to the start, and get a string counted by $f_{11}(n+1)$. 


This means that both $f_{011}(n+1)$ and $f_{11}(n+1)$ should have an $f_{11}(n)$ term. We do the same thing for all three other cases.

Depending on how you want to solve the recurrence, this is good enough. For example, we can write this down as a matrix recurrence $$\begin{bmatrix} f_\varnothing(n+1) \\ f_1(n+1) \\ f_{11}(n+1) \\ f_{011}(n+1)\end{bmatrix} = \begin{bmatrix}1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0\end{bmatrix}\begin{bmatrix} f_\varnothing(n) \\ f_1(n) \\ f_{11}(n) \\ f_{011}(n)\end{bmatrix}$$ and one way to solve a linear recurrence is to put everything into a matrix anyway.
A: This answer is based upon the Goulden-Jackson Cluster Method which is a convenient technique to derive a generating function for problems of this kind. A recurrence relation can then be derived easily.

We consider words of length $m\geq 0$ built from a binary alphabet $$\mathcal{V}=\{0,1\}$$ and the set $B=\{0011\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^m$ being  the number of searched words of length $m$.

According to the paper (p.7) the generating function $f(s)$  is
\begin{align*}
f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}
\end{align*}
with $d=|\mathcal{V}|=2$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[0011])
\end{align*}

We calculate according to the paper
  \begin{align*}
\text{weight}(\mathcal{C}[0011])&=-s^4\\
\end{align*}
and obtain
\begin{align*}
\color{blue}{f(s)}&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\
&\color{blue}{=\frac{1}{1-2s+s^4}}\tag{1}\\
\end{align*}

From the generating function $f(s)=\sum_{m=0}^\infty a_m s^m$ stated in (1) we can derive the recurrence relation easily.

We obtain from (1)
  \begin{align*}
f(s)=1+(2s-s^4)f(s)
\end{align*}
and we conclude
  \begin{align*}
\color{blue}{a_m}&=[s^m]f(s)\\
&=[s^m]\left(1+(2s-s^4)f(s)\right)\\
&=
\begin{cases}
&\color{blue}{=1}&\qquad m=0\\
2[s^{m-1}]f(s)&\color{blue}{=2a_{m-1}}&\qquad m=1,2,3\\
(2[s^{m-1}]-[s^{m-4}])f(s)&\color{blue}{=2a_{m-1}-a_{m-4}}&\qquad m\geq 4
\end{cases}
\end{align*}

A: One problem is with iii):  the $f(n-3)$ includes strings starting with 11... (and otherwise contain no 0011), but putting 000 in front of that gives you 00011... i.e. it contains a 0011
Likewise, for iv): $f(n-4)$ includes strings starting with 011... and putting 0010 in front of that gives you 0010011... i.e. also a 0011
