Recurrence relation for the number of bit strings of length n that have a pair of consecutive zeros (at least one pair of consecutive zeros) I understand that this question exists in many forms on this site. However, the intent of my question is not to seek an answer but to find out where I went wrong in my thinking. 
What I have to find:
Recurrence relation for the number of bit strings of length n that have a pair of consecutive zeros (at least one pair of consecutive zeros). Bit strings are binary strings containing only ones and zeros (Example - 110001100101)
What I have tried:
My line of reasoning is as follows
Let $a_n$ be the number of bit strings of length n which have a pair of consecutive zeros. If the number of bit strings of length $(n-1)$ having a pair of consecutive zeros is $a_{n-1}$, we can add either a 1 or 0 in the end to get a bit string of length n which satisfies our condition. So far our equation looks like this using product rule
$a_n$ = $2a_{n-1}$
Now suppose we have a string of length $(n-1)$ which does not have a pair of consecutive zeros.
Case 1: Last digit is $1$. No matter what we add in the end, the resulting string won't have a pair of consecutive zeros.
Case 2: Last digit i.e $(n-1)^{th}$ digit is $0$. If we add a zero in the end, the resulting string will have a pair of consecutive zeros. However, we should count this string only if the previous $(n-2)$ digits don't have a pair of consecutive zeros. Let $a_{n-2}$ be a bit string of length $(n-2)$ which has a pair of consecutive zeros. Then number of bit strings of length $(n-2)$ which don't have a pair of consecutive zeros is $2^{n-2} - a_{n-2}$. 
Thus our final equation is 
$a_n$ = $2a_{n-1} + 2^{n-2} - a_{n-2}$
Solution given in the book:
Let $a_n$ be the number of bit strings of length $n$ containing a pair of consecutive $0$'s. In order to construct a bit string of length $n$ containing a pair of consecutive $0$'s we could start with $1$ and follow with a string
of length $n - 1$ containing a pair of consecutive 0's, or we could start with a $01$ and follow with a string of length $n - 2$ containing a pair of consecutive $0$'s, or we could start with a $00$ and follow with any string
of length $n - 2$. These three cases are mutually exclusive and exhaust the possibilities for how the string might start. From this analysis we can immediately write down the 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 of length k.) 
What is my question
I admit that the solution given in book is easier to follow than mine. Nevertheless, I would like to know where I went wrong in my thinking. My equation doesn't give the right answers. Thank you.
 A: The problem with your argument is that a sequence with length $n - 2$ that does not contain two consecutive zeros but ends with a zero can be extended to one that does contain two consecutive zeros by appending a single zero, which places it among the $a_{n - 1}$ admissible strings of length $n - 1$.
Let's examine admissible strings of length $4$.  They are the eight strings
$$0000, 0001, 0010, 0100, 1000, 0011, 1001, 1100$$ 
Notice that since the admissible strings of length $3$ are 
$$000, 001, 100$$
you counted the six strings
$$0000, 0001, 0010, 0011, 1000, 1001$$
in your $2a_3$ admissible strings of length $4$ that can be formed by appending a $0$ or $1$ to the end of an admissible string of length $3$.
Since the inadmissible strings of length $2$ are 
$$01, 10, 11$$
you counted the three strings 
$$0100, 1000, 1100$$
among the $2^{n - 2} - a_{n - 2}$ among the admissible strings of length $4$ that can be formed by appending $00$ to an inadmissible string of length $2$.
Notice that you have counted the string $1000$ twice since $100$ is an admissible string of length $3$ and $10$ is an inadmissible string of length $2$.  The problem, as stated above, is that $10$ is an inadmissible string of length $2$ that can be extended to an admissible string of length $3$ by appending a $0$ to the end of an inadmissible string of length $2$ that ends in a zero.
