Consider the following:

Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s.

I am trying to understand the solution to this problem, but I am stuck on this line of the solution:

To obtain a recurrence relation for {an}, note that by the sum rule, the number of bit strings of length n that do not have two consecutive 0s equals the number of such bit strings ending with a 0 plus the number of such bit strings ending with a 1.

I don't understand why this is the case. For example, what if you have a bit string 000, it ends in 0, but has 2 consecutive 0s.

Could someone help me understand this?

  • 2
    $\begingroup$ I think the paragraph probably meant "the number of such strings ending in $0$..." That is, we can split this sort of strings into a list of those that end with $0$ and those that don't. $\endgroup$ – Thomas Andrews Oct 18 '16 at 18:07
  • $\begingroup$ I agree with @ThomasAndrews. The number of such strings should be given by the Fibonacci sequence, see this. $\endgroup$ – Bobson Dugnutt Oct 18 '16 at 18:12

So, if you read it carefully, you'll see that it says the following:

  • there is a certain set $S$ of length-$n$ bit strings that don't contain two consecutive 0s
  • each $s\in S$ either ends with 0 or with 1
  • thus, if $S_1\subset S$ are those ending in 1 and $S_0\subset S$ are those ending in 0, we have $S = S_0\cup S_1$ as a disjoint union
  • so, $|S_1| + |S_2| = |S|$
| cite | improve this answer | |

Lets give it a shot:

  1. There are $2^n$ bit-strings of length $n.$
  2. The number of bit-strings with NO 2 consecutive zeroes is $= 2^n -$ (no of bit-strings with consecutive zeroes)
  3. Suppose string x of length n has consecutive zeroes
  4. Then for $1\le k \le n-1$, where $k$ is the position of in bit-string $x$, $x(k) = x(k + 1) = 0$ that is the value of the bit in both these positions is $0.$

We are now assured of a bit-string with at least one pair of consecutive zeroes. Further, we have included all bit-strings with more than one pair of consecutive zeroes.

  1. Since $k$ can be fixed to any of $n-1$ positions

  2. And each position value $k$ is associated with $2^{n-2}$ different bit-strings.

We have occupied positions k and k+1 with zeroes and have ($n-2$) free variables(positions).

  1. By the product rule, the number of bit-strings which surely have at least one pair of consecutive zeros is $(n-1) * 2^{n-2}$

It the product of possible choices for k and the number of bit-strings associated with each choice of k.

  1. Consequently, the number of bit-strings of length n with NO consecutive zeroes is

    $2^n - (n-1)*2^{n-2}.$

Any comments! I would like to know if there are faults in the logic.

| cite | improve this answer | |

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.