1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.