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!

  • $\begingroup$ If $n=3$...shouldn't there be exactly $1$ such string (namely $000$)? But you have $a(3)=2a(2)+2^2-a(-1)=4$. $\endgroup$ – lulu Oct 31 '16 at 12:13
  • 1
    $\begingroup$ I think the correct recurrence relation is a(n)=a(n-1)+a(n-2)+a(n-3)+2^(n-3). $\endgroup$ – Rohan Oct 31 '16 at 12:16
  • $\begingroup$ i think a(3) will have a value equals 1 , a(1) =0 , a(2)=0 , these will be the values which we may use to find a(4) and other strings greater than that $\endgroup$ – srishti77714 Oct 31 '16 at 12:18
  • $\begingroup$ Do you mean atleast 3 zeroes or exactly three consecutive zeroes? If the former, just subtract the remaining cases from $2^n$ .If the latter, you just need to chose the position of the first 0. $\endgroup$ – bat_of_doom Oct 31 '16 at 12:20
  • $\begingroup$ Well...$a(4)=3$, no? We just have $0000,0001,1000$. But you get $a(4)=2a(3)+8-a(0)=2+8=10$. $\endgroup$ – lulu Oct 31 '16 at 12:20

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.


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.}}\;.$$


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.