# How many bit-strings of length 7 have exactly 2 consecutive zeros

I suspect this problem involves a recurrence relation, but I can't figure out how to start... Can someone help me?

thanks!

-
Does 0000000 count? How about 1000111? –  Guess who it is. Oct 1 '11 at 23:15
@J.M. I think both of those have more than one instance of two consecutive zeros, i.e. ..(00)0.. and ..0(00).. are distinct examples. –  anon Oct 1 '11 at 23:19
Well, I was kind of wondering which of 0000000,1000000, or 1111100 would be "first"... –  Guess who it is. Oct 1 '11 at 23:23
0000000 does not count, as it has 7 consecutive zeros. The elements being counted are: 0011111, 0011110, 0011101, 0011010, and so on –  marcos Oct 1 '11 at 23:33

There’s no real need to look for a recurrence when you want the answer only for a single short length. $7$ is so small that it’s probably easiest to do it by hand. The cases are $001xxxx$, $1001xxx$, $x1001xx$, and their mirror images.

• $x1001xx$: The first bit is arbitrary, and the last two can be anything but $00$, for a total of $2\cdot 3=6$ strings.

• $1001xxx$: How many of the $8$ possible continuations are ruled out?

• $001xxxx$: Break this into the subcases $0011xxx$ and $0010xxx$ and use what you’ve already done.

Don’t forget to double to account for the mirror images. Does this count anything twice (i.e., is any acceptable string its own mirror image)?

If you need the general solution, Ross’s approach is as straightforward as any.

-

Hint: If you let A(n) be the number of n-bit strings without two consecutive zeros and ending in 1, B(n) be the number of n-bit strings with two consecutive zeros and ending in 1, C(n) be the number of n-bit strings without two consecutive zeros and ending in 0, D(n) be the number of n-bit strings with two consecutive zeros and ending in 0, you can set up a set of linked recurrences. Imagine adding each of 1 and 0 to each type of string and find where it goes. Then your final answer is B(7)+D(7). A good check is to define E(n) as the number of strings that have failed, either by having three zeros in a row or having two sets of two. Then you should have accounted for all the strings.

-