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? –  Ｊ. Ｍ. 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"... –  Ｊ. Ｍ. 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.

-