Why is the recurrence relation for finding the # of bit strings of length n that contains a pair of 2 consecutive 0's…?

Question

$$a_n = a_{n-1} + a_{n-2} + 2^{n-2} \text{ ?}$$

The solution manual states,

Let $a_n$ be the number of bit strings of length $n$ containing a pair of consecutive $O$s. In order to construct a bit string of length $n$ containing a pair of consecutive $O$s we could start with $1$ and follow with a string of length $n - 1$ containing a pair of consecutive $O$s, or we could start with a $01$ and follow with a string of length $n - 2$ containing a pair of consecutive $O$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.

How come it doesn't account for when a bit string of length $n$ could start with $0$ and follow with a string of length $n-1$ or $10$ and $n-2$ or $1$1 and follow with a string of length $n-2$, thus making it $$a_n = 2a_{n-1} + 4a_{n-2} \text{ ?}$$

Furthermore where did the $2^{n-2}$ come from?

Answer 1

The first two bits of the string can be $00, 01, 10, $ or $11$ If they are $00$, we have satisfied the requirement for $00$ somewhere, so we can append any string of $n-2$ bits. There are $2^{n-2}$ of these. If it starts with $1$ (covering my cases $10$ and $11$) you need to append a string of length $n-1$ that includes $00$, of which there are $a_{n-1}$. If it starts with $01$, you need to append a string of length $n-2$ that includes $00$, of which there are $a_{n-2}$

In your computation, if you start with $0$ it matters whether the next bit is $0$ as well. Your cases are not disjoint, so adding them is not correct.