# Understanding why this simple recurrence relation is structured in this manner

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.

• There are $2^{n-2}$ "good" strings of length $n$ that start with $00$. – André Nicolas Jun 22 '16 at 23:30
• @AndréNicolas Ok but there are also the same number of "good" strings that start with $01$ as well, yet we account for that with the $a_{n-2}$ term without using the exponential. – Dave Jun 22 '16 at 23:41
• No, the number of good strings that start with $01$ is $a_{n-2}$, because we are essentially starting again. It is not $2^{n-2}$, because a number of the ways of "completing" $01$ by appending a string of length $n-2$ lead to $n$-strings with no consecutive $0$'s. However, once we have $00$ as a start, any completion will do the job. – André Nicolas Jun 22 '16 at 23:47
• @AndréNicolas So are you saying that $00$ can be considered as a "fourth case" then? What motivated the original choice of $1$, $01$, and $10$? The reason I'm asking is because it seems arbitrary to choose three starting conditions, instead of two ($0$ and $1$) or four ($00$, $01$ , $10$, $11$). And on that note, why wasn't $11$ a case to consider? – Dave Jun 22 '16 at 23:59
• To clarify, I'm saying the textbook is starting at two different positions (the first digit, or the first two digits) and then only picking what appears to be an arbitrary subset of the possible values of the string at those positions. – Dave Jun 23 '16 at 0:01

## 1 Answer

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.