Given this question:
Find a recurrence relation for the number of bit strings of length $n$ that contain a pair of consecutive $0$s.
And this textbook answer:
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. From this analysis we can immediately write down the recurrence relation, valid for all $n \ge 2: a_n = a_{n-l} + a_{n-2} + 2^{n-2}$. (Recall that there are $2^k$ bit strings of length $k$.)
What is the reasoning behind the three cases chosen here? Why do we care about starting with $01$ and $10$? I would think if anything we would only care about two cases, a string starting with $0$ and a string starting with $1$, both of which would leave $n-1$ remaining for each and thus $2a_{n-1} + 2^{n-1}$ in the recurrence relation.
I also completely missed why they added $2^{n-2}$ at the end -- I thought the purpose of the recurrence relation was to assume the lower terms in the sequence $n-1, n-2, ...$ etc. are all valid and just recurse down to them until we reach the base case. But here they add the number of permutations explicitly at the end. So what did I misunderstand here?
Thanks for any insight, it is very much appreciated.
I assume you are OK with the idea that if we start with a $1$ then we need to have a zero-pair among one fewer bits, thus there are $a_{n-1}$ good strings. So Let's see what happens if we start with a $0$.
We might have a $1$ next, in which case we have "wasted" that starting zero, and have lost two bits, so there are only $a_{n-2}$ good strings start with that $01$.
Or we might have a zero next, and not only have we not wasted the starting zero, we are automatically a good string. In that case we can enjoy $2^{n-2}$ ways to choose the remaining $n-2$ bits defining our string.
Add those up to get $$ a_n = a_{n-1} + a_{n-2} + 2^{n-2} $$ with $a_0 = 0, a_1 = 1$.
Now lets examine $b_n = 2^n-a_n$. A little algebra (using $2^{n-1} + 2^{n-2} + 2^{n-2} = 2^n$) tells us that $$b_n = b_{n-1}+b_{n-2}$ and we have $b_0 = 1, b_1 = 2$.
So the closed form for $a_n$ is just $2^n$ minus the $n$-th Fibonacci number $F_n$, where we use the convention that $F_1 = F_2 = 1$.
And that, in turn, means that the problem of finding the number of bit strings without two consecutive zeros is a more intuitive problem.