Finding Recurrence Relation for Bit Strings with Consecutive Zeros

1 reply · 2K views · last reply
Miike012
Messages
1,009
Reaction score
0
I am having difficulty knowing which "cases" include in the recurrence equation.

My solution to problem in paint document.

Cases 1 - 6:
All cases contain strings of length n
Let ak represent number of bit string of length k with a pair of consecutive 0s.

For cases 1 and 2.
an-1, k = n-1.

1. Start with 0
0_ _ ... _
2. Start with 1
1_ _ ... _

For cases 3 - 5
an-2, k = n-2.

3. Start with 1 0
1 0 _ ... _
4. Start with 1 1
1 1 _ ... _
5. Start with 0 1
0 1 _ ... _

Case 6
an-2 = 2n-2

6. Start with 0 0
0 0 _ ... _

Therefore
An = (sum of ak from case 1 and 2) + (sum of ak from case 3,4, and 5) + (ak from case 6) =
2(an-1) + 3(an-2) + 2n-2

Cases that "overlap"
1 and 5: if second term of case 1 is 1
1 and 6: if second term of case 1 is 0

2 and 3: if second term of case 2 is 0
2 and 4: if second term of case 2 is 1

Therefore
an = 2(an-1) - (an-2) + 2n-2 = An - 4(an-2)
 
Attachments
  • Typeset problem statement reading: Find a recurrence relation for the number of bit strings of length n that contain a pair of consecutive 0s. Below it, an Answer label with the recurrence a_n = a_{n-1} + a_{n-2} + 2^{n-2}.
    QQQQ.jpg
    4.6 KB · Views: 493
Last edited:
I couldn't follow how you got your final equation from the various cases.
But it's much simpler if you just consider three mutually exclusive cases instead of having to subtract out overlaps. What are the three cases?