0

Here is a question that states Bn is the number of bit strings with length n>=1 that don't contain any maximal run of ones of odd length, they're all even. I know how to do the first question but not sure how to go about the second question. Any help should lead me in the right direction, thanks!

enter image description here

crazed5x
  • 1
  • @mvw I got: B1 = 0, B2 = 11 or 00, B3 = 110 or 011 or 000 – crazed5x Feb 12 '15 at 19:38
  • @crazed5x: It would be worth the effort to try to calculate at least $B_4$ and $B_5$, and preferably $B_6$ as well. If you do this correctly, you should either recognize the sequence of numbers that you’re getting or spot a useful pattern in it. The pattern gives a good clue for approaching the second part of the problem. Try it on your own first; if you still can’t make any headway, look at this answer. – Brian M. Scott Feb 12 '15 at 19:46
  • So $B_1 = 1$, $B_2 = 2$, $B_3 = 3$, and of course $B_0 = 1$ for the empty word $\epsilon$. – mvw Feb 12 '15 at 21:18

1 Answers1

0

To come up with a recursive scheme, one has to analyze what is changing from $n$ to $n+1$.

After writing down the first three rounds with bit strings of length $1$, $2$ and $3$ and observing what changes to the strings occur if one adds a $0$ or a $1$ it turns out that one can divide the words into three categories and assign counters:

  • fine $F$, e.g. $00$, $\lvert F\rvert = B_n$
  • flawed but recoverable $R$, e.g. $01$, $\lvert R \rvert = R_n$
  • flawed and lost $L$, e.g. $10$, $\lvert L \rvert = L_n$

The following table shows what happens to the result if one adds a $0$ or a $1$ to words from these sets:

$$ \begin{array}{rcll} F \cdot 0 & \to & F & \mbox{stays fine} \\ F \cdot 1 & \to & R & \mbox{gets flawed, but recoverable} \\ R \cdot 0 & \to & L & \mbox{gets lost forever} \\ R \cdot 1 & \to & F & \mbox{recovered!} \\ L \cdot 0 & \to & L & \mbox{stays lost} \\ L \cdot 1 & \to & L & \mbox{stays lost} \end{array} $$

This gives the following updates of the counts: \begin{align} B_{n+1} &= B_n + R_n \\ R_{n+1} &= B_n \\ L_{n+1} &= 2 L_n + R_n \end{align}

Combining the second with the first we get a recurrence relation for $B_n$: $$ B_{n+1} = B_n + B_{n-1} $$ This is a well known recurrence relation, with explicit solutions for $B_n$.

So we can calculate $R_n = B_{n-1}$ and $L_n = 2^n - (B_n + R_n) = 2^n - B_{n+1}$.

From the paper examples we note that $B_1 = R_1 = 1$, $L_1 = 0$ and $B_2 = 2$, $R_2 = L_2 = 1$ and $B_3 = L_3 = 3$, $R_3 = 2$.

mvw
  • 34,562