Number of binary strings of length n that do not contain a particular substring?

Question

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.

Answer 1

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)$.

Answer 2

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$.