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$ Oct 18, 2016 at 18:07
  • $\begingroup$ I agree with @ThomasAndrews. The number of such strings should be given by the Fibonacci sequence, see this. $\endgroup$ Oct 18, 2016 at 18:12

3 Answers 3


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

This is an old question, but the answer might be helpful to someone. Suppose that $a_n$ gives the number of binary sequences of length $n$ without consecutive 0s. Then we can always add 1 to the end of the sequence to make a sequence of length $n+1$ without consecutive zeros. We can only add a 0 to the end if the sequence ends with a 1, but we can add 10 to the end of any sequence without having consecutive zeros. Hence $$ a_{n+1}=a_n+a_{n-1},\quad a_0 = 1, a_1 = 2. $$


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .