I am trying to count the number of bit-strings of length 8 with 3 consecutive zeros or 4 consecutive ones. I was able to calculate it, but I am overcounting. The correct answer is $147$, I got $148$.
I calculated it as follows:
Number of strings with 3 consecutive zeros = $2^5+5\times2^4 = 112$, because the 3 zeros can start at bit number 1, 2, 3, .., 6
Number of strings with 4 consecutive ones = $2^4+4\times2^3 = 48$, I used the same reasoning.
Now I am trying to count the number of bit-strings that contain both 3 consecutive zeros and 4 consecutive 1s. I reasoned as follows:
the strings can be of the following forms: 0001111x, 000x1111, x0001111..thus there are $2+2+2 = 6$ possibilities for bit-strings where the 3 consecutive zeros come first. Symmetrically there are $6$ bit-strings where the 4 consecutive ones come first.
Thus the answer should be = $112+48-12 = 148$.
clearly there's something wrong with my reasoning, if someone could point it out, that would be awesome. Thanks