I'm pulling my hair out over a review question for my final tomorrow.
Find a recurrence relation (and its initial conditions) for the number of bit strings of length n that contain two consecutive 1s.
Here is my thought process/work, could someone please help me figure out where I'm going wrong?
Knowing that a bit string of length 0 or 1 cannot contain two consecutive bits of any kind, and that only one bit string of length 2 (the string 11) can contain two consecutive ones, I have the initial conditions
a(0) = 0,
a(1) = 0, and
a(2) = 1. I'm now trying to find a formula for the term
I know there are three ways for a bit string of length
n + 2 to have two consecutive 1s:
n + 1and
n + 2are 1.
count(X) = 2^nbecause this still leaves
nbits unaccounted for.
n + 1are 1.
count(Y) = 2^nfor the same reason.
Z: The first
nbits contain 11 somewhere.
count(Z) = 4 * a(n)because adding 2 bits to the
a(n)condition quadruples the number of possible strings.
Since these three conditions are not mutually exclusive,
a(n+2) count(X) + count(Y) + count(Z) - (count(X $\cup$ Y) + count(X $\cap$ Z) + count(Y $\cap$ Z)) + count($X \cap Y \cap Z)$
a(n+2) = 2^n + 2^n + 4 * a(n) - (2^(n-1) + a(n) + 2 * a(n-1)) + a(n-1)
This successfully proves the initial condition
a(2) = 1 and the next one -
a(3) = 3. But when I plug in 4, I get 9. Listing out the possible strings by hand and circling the ones that satisfy the condition gives only 8. What am I doing wrong?