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)

Question

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.

Answer 1

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.