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