[Math] Recurrence Relation for Bit String Length n with No Consecutive 0s

discrete mathematicsrecurrence-relations

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?

Best Answer

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