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

• Hint; first show that, unless the sequence consists of all $1's$, it must end in either $0$ or $01$ – lulu Feb 19 at 1:23

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

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

• Looks like you lost a factor of $x^2$ in the second term on the RHS of the last equation. – RobPratt Feb 19 at 4:32