- #1
Miike012
- 1,009
- 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)
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
Last edited: