How can one come up with this recursion formula?

Question

How many $n$ bit strings are there that contain 3 consecutive 0's?

I found a recursion formula to get to the answer of the above question. $$a(n)=2a(n-1) + 2^{n-4} - a(n-4)$$ where $a(n)$ is the number of $n$ bit strings containing 3 consecutive 0's. Why is this so?

Please forgive me if this is a stupid question, I am a newbie!

Answer 1

Let $b(n)$ denote the number of bad strings of length $n$ (that is, those strings of length $n$ which do not contain $000$)

It is easier to get a recursion on the bad strings. To see that, divide $b(n)$ into three types according to the last character. Specifically:

Let $r(n)$ denote the number of bad strings of length $n$ that end in $1$

Let $s(n)$ denote the number of bad strings of length $n$ that end in $10$

Let $t(n)$ denote the number of bad strings of length $n$ that end in $100$

Then $b(n)=r(n)+s(n)+t(n)$. Recursively we get: $$r(n)=b(n-1)\quad s(n)=r(n-1)=b(n-2)\quad t(n)=s(n-2)=b(n-2)$$ whence $b(n)=b(n-1)+b(n-2)+b(n-3)$

to connect this to your recursion, we remark that we can write this as $$b(n-1)+b(n-2)=b(n)-b(n-3)\implies b(n-2)+b(n-3)=b(n-1)-b(n-4)$$ Thus we get $$b(n)=b(n-1)+\left(b(n-1)-b(n-4)\right)=2b(n-1)-b(n-4)$$

Now $a(n)=2^n-b(n)$ so we get $$a(n)=2^n-2\times(2^{n-1}-a(n-1))+(2^{n-4}-a(n-4))=2a(n-1)+2^{n-4}-a(n-4)$$ as desired.

Answer 2

Say that a bit string is good if it contains the substring $000$ and bad if it does not. Let $\sigma$ be a good bit string of length $n$, and let $\sigma'$ be the substring consisting of the first $n-1$ bits of $\sigma$. There are two possibilities:

• $\sigma'$ is good, or
• $\sigma'$ is bad, and $\sigma$ ends with $000$.

These two possibilities are mutually exclusive: every good string of length $n$ is in exactly one of these two categories. We’ll count the $n$-bit strings in each category.

If $\sigma'$ is good, we get a get a good $n$-bit string by appending either $0$ or $1$: $\sigma$ can be either $\sigma'0$ or $\sigma'1$. Thus, each of the $a(n-1)$ good strings of length $n-1$ produces $2$ good $n$-bit strings, both in the first category above. This is the only way to get $n$-bit strings in that category, so there are $2a(n-1)$ good $n$-bit strings of that kind.

Now suppose that $\sigma'$ is bad, and that $\sigma$ ends in $00$. This means that $\sigma'$ must end in $100$: it must end in $00$ in order for $\sigma$ to end in $000$, and it can’t end in $000$, because then it would be good, and we’re assuming that it isn’t. Let $\tau$ be the part of $\sigma'$ that’s left after we remove the final $100$; $\tau$ has length $n-4$, and it can be any bad string of length $n-4$. Every $n$-bit string $\sigma$ in this second category arises in this way: by appending $1000$ to a bad $(n-4)$-bit string $\tau$. There are altogether $2^{n-4}$ bit strings of length $n-4$, and $a(n-4)$ of them are good, so there are $2^{n-4}-a(n-4)$ bad strings of length $n-4$. Each of them gives rise to one good $n$-bit string in the second category, so there are $2^{n-4}-a(n-4)$ good $n$-bit strings in that category.

The total number of good $n$-bit strings is the sum of the numbers in the two categories:

$$a(n)=\underbrace{2a(n-1)}_{1\text{-st cat.}}+\underbrace{2^{n-4}-a(n-4)}_{2\text{-nd cat.}}\;.$$