1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

The first two bits of the string can be $00, 01, 10, $ or $11$ If they are $00$, we have satisfied the requirement for $00$ somewhere, so we can append any string of $n-2$ bits. There are $2^{n-2}$ of these. If it starts with $1$ (covering my cases $10$ and $11$) you need to append a string of length $n-1$ that includes $00$, of which there are $a_{n-1}$. If it starts with $01$, you need to append a string of length $n-2$ that includes $00$, of which there are $a_{n-2}$

In your computation, if you start with $0$ it matters whether the next bit is $0$ as well. Your cases are not disjoint, so adding them is not correct.

| cite | improve this answer | |
$\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.