# Recurrence Relation for Bit String Length n with No Consecutive 0s

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?

• 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. – Thomas Andrews Oct 18 '16 at 18:07
• I agree with @ThomasAndrews. The number of such strings should be given by the Fibonacci sequence, see this. – 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|$

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.