Finding Recurrence Relation

1. Dec 4, 2013

Miike012

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.

0_ _ ... _
1_ _ ... _

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

1 0 _ ... _
1 1 _ ... _
0 1 _ ... _

Case 6
an-2 = 2n-2

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)

Attached Files:

• QQQQ.jpg
File size:
4.6 KB
Views:
87
Last edited: Dec 4, 2013
2. Dec 4, 2013

haruspex

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?