Number of binary strings of length n that do not contain a particular substring? Let $A_n$ denote the set of strings of elements of the set {0, 1} of length $n$. Let $B_n$ be those strings in $A_n$ which do not contain $0,1,1$ as a sub-string (in consecutive positions). Let $b_n = |B_n|$.
Prove that for $n\geq4$ we have $b_n =b_{n−1}+b_{n−2}+1$. Furthermore, determine the generating function for this sequence.
I tried to prove the recurrence relation in the first part via induction, but ran into a tricky situation where I had to consider the number of substrings that started with $1,1$ and that got me nowhere. I tried to skip over that and determine the generating function by assuming that the recurrence relation was true and got $f(x)=\sum\limits_{n=0}^{\infty}b_nx^n=-\frac{1}{1-x}*\frac{1}{x^2+x-1}$ by considering $f(x)+xf(x)+\frac{1}{1-x}$ but I'm also unsure of what to do with my result.
I feel that I'm missing some key insight (or maybe just making a silly algebra error) in my work, and was wondering how others might go about this problem.
 A: Let $c_n$ and $d_n$ be the number of 011-avoiding $n$-strings that end with 0 and 1, respectively.  Then $c_0=c_1=d_0=d_1=1$, $d_2=2$, and, by conditioning on the length $k$ of the last run, we see that
\begin{align}
c_n &= \sum_{k=1}^n d_{n-k} &&\text{for $n \ge 1$}\\
d_n &= c_{n-1} + 1 &&\text{for $n \ge 3$}
\end{align}
Let $C(z)=\sum_{n=0}^\infty c_n z^n$ and $D(z)=\sum_{n=0}^\infty d_n z^n$.  Then the recurrence relations imply
\begin{align}
C(z)-1 &= \frac{z}{1-z} D(z) \\
D(z)-1-z-2z^2 &= z(C(z)-1-z) + \frac{z^3}{1-z}
\end{align}
Solving for $C(z)$ and $D(z)$ yields
\begin{align}
C(z) &= \frac{1-z+z^3}{1-2z+z^3}\\
D(z) &= \frac{1}{1-z-z^2}
\end{align}
The desired generating function is then (subtracting $1z_0$ for the empty string that is otherwise counted twice)
$$C(z)+D(z)-1=\frac{1}{1-2z+z^3}=\frac{1}{(1-z)(1-z-z^2)},$$
which is OEIS A000071.
Note that the denominator implies the recurrence relation $b_n=2b_{n-1}-b_{n-3}$ for $n \ge 3$. 
A: As lulu points out in a comment: First note that if the binary string ends with $11$ then it must consist entirely of $1$'s.
Let $x_n$ denote the number of binary strings that end with $0$ (that avoid $011$).
Let $y_n$ denote the number of binary strings that end with $01$ (that avoid $011$).
It is then easy to set up the following recurrence relations
\begin{eqnarray*}
b_n&=&x_n+y_n+1 \\
x_{n+1}&=&x_n+y_n+1 \\
y_{n+1}&=&x_n.
\end{eqnarray*}
Grind through the algebra and we have $b_{n}=b_{n-1}+b_{n-2}+1$.
Now multiply this equation by $x^n$ and sum from $n=2$ up to $ \infty$ and we have
\begin{eqnarray*}
\sum_{n=2}^{\infty} b_{n} x^n= \sum_{n=2}^{\infty} b_{n-1} x^n+ \sum_{n=2}^{\infty} b_{n-2} x^n+ \sum_{n=2}^{\infty}x^n \\
f(x)-1-2x =x(f(x)-1) +x^2f(x)+\frac{x^2}{1-x}.
\end{eqnarray*}
It is now a hop & skip derive a formula for $f(x)$.
