Recurrence relation for number of bit strings of length n that contain two consecutive 1s 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 a(n+2).
I know there are three ways for a bit string of length n + 2 to have two consecutive 1s:


*

*Condition X: Both n + 1 and n + 2 are 1. count(X) = 2^n because this still leaves n bits unaccounted for.

*Condition Y: Both n and n + 1 are 1. count(Y) = 2^n for the same reason.

*Condition Z: The first n bits 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)$

or 
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?
Thanks.
 A: Here's an alternate way of solving your question.
Let $a_n$ be the number of bit strings of length $n$ containing a pair of consecutive $1$'s.
In order to construct such a bit string, one could start with


*

*$0$ and follow with a string of length $(n-1)$ containing a pair of consecutive $1$'s

*$10$ and follow with a string of length $(n-2)$ containing a pair of consecutive $1$'s

*$11$ and follow with any string of length $(n-2)$


Since these three cases are mutually exclusive and exhaust the possibilities for how such a string might start, we can apply the sum rule and write down the following recurrence relation valid for all  $n \ge 2;$
$a_n = a_{n-1} + a_{n-2} + 2^{n-2}$
(Recall that there are $2^k$ bit strings on length $k$).
Now for the initial conditions:


*

*$a_0 = 0$

*$a_1 = 0$

A: A perhaps less complicated way of solving the problem is to let $b_n$ be the number of length $n$ bit strings with no consecutive $1$'s. It is easy to show that
$$b_{n+2}=b_{n+1}+b_n.$$
Since $b_k=2^k-a_k$, substitution and a little simplification give
$$a_{n+2}=a_{n+1}+a_n+2^n.$$
A: Your count of $Y \cap Z$ requires that the two $1$'s in $Z$ be in the first $n-1$ bits.  For $n=4$ it does not include $001110$
