1
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Looks like you lost a factor of $x^2$ in the second term on the RHS of the last equation. $\endgroup$ – RobPratt Feb 19 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.