Finding Recurrence Relation for Bit Strings with Consecutive Zeros

[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 a_k represent number of bit string of length k with a pair of consecutive 0s.

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

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

For cases 3 - 5
a_n-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
a_n-2 = 2^n-2

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

Therefore
A_n = (sum of a_k from case 1 and 2) + (sum of a_k from case 3,4, and 5) + (a_k from case 6) =
2(a_n-1) + 3(a_n-2) + 2^n-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
a_n = 2(a_n-1) - (a_n-2) + 2^n-2 = A_n - 4(a_n-2)

 

[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?