# How do I find the number of bit strings with 3 consecutive 0s in a bit string of length n?

Say n is 8.

How would I ever solve this problem? I've Googled around and searched this site but I haven't come up with much. I'm not even looking for the answer necessarily, just the process by which I'd go about getting it.

I started by calculating the total number of bit strings of length 8 as $2^8$. From there where should I go?

-
Would you count $0000$ as containing 3 consecutive $0$s or are you limiting the count to those strings that contain 3 consecutive $0$s and no more? –  Rick Decker Jan 15 '13 at 21:56

You can define $A(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in $1$, $B(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in one $0$, , $C(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in two $0$'s, and $D(n)$ as the number of strings of length $n$ containing three zeros. Then $A(1)=1$, $B(1)=1$, $C(1)=0$, $D(1)=0$ and for $n>1$, \begin{align} A(n)&=A(n-1)+B(n-1)+C(n-1) \\ B(n)&=A(n-1)\\ C(n)&=B(n-1)\\ D(n)&=2D(n-1)+C(n-1) \end{align}
Unless I misread, I got $D(4)=2$ but there are three such strings of length 4: $0000$, $0001$, $1000$. –  Rick Decker Jan 15 '13 at 22:18
@RickDecker: Yes, I lost the coefficient of $2$ on $D$. You can add either a zero or one to a string that already has three zeros. –  Ross Millikan Jan 15 '13 at 22:20