Number of bit strings with 3 consecutive zeros or 4 consecutive 1s 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

Let $n$ be a nonnegative integer. Let $a_n$ be the number of bit strings of length $n$ with at least 3 consecutive zeros. Clearly $a_0 = 0$, $a_1 = 0$, $a_2 = 0.$ Let $n \geq 3.$  Denote by $S$ the set of all bit strings of length $n$ with at least 3 consecutive zeros. The set $S$ is a disjoint union of the following four sets: 


*

*$S_3$ the set of all bit strings of length $n$ that end with $000$, 

*$S_2$ the set of all bit strings in $S$ that end with $100$,

*$S_1$ the set of all bit strings in $S$ that end with $10$,

*$S_0$ the set of all bit strings in $S$ that end with $1$.


These sets have the following cardinalities: $|S_3| = 2^{n-3}$, $|S_2| = a_{n-3}$, $|S_1| = a_{n-2}$, $|S_0| = a_{n-1}$. Since $|S| =a_n$, by the sum rule
$$
a_n = 2^{n-3} + a_{n-3} + a_{n-2} + a_{n-1}. 
$$
Since $a_0 = 0$, $a_1 = 0$, $a_2 = 0$, we have 
\begin{align*}
a_3 & = 2^0 + 0 + 0 + 0 = 1\\
a_4 & = 2^1 + 0 + 0 + 1 = 3\\
a_5 & = 2^2 + 0 + 1 + 3 = 8\\
a_6 & = 2^3 + 1 + 3 + 8 = 20\\
a_7 & = 2^4 + 3 + 8 + 20 = 47\\
a_8 & = 2^5 + 8 + 20 + 47 = 107. 
\end{align*} 
For bit strings with at least 4 consecutive ones, the same reasoning leads to the recursion 
$$
b_0 = b_1 = b_2 = b_3 = 0, \quad b_n=2^{n-4}+b_{n-4}+ b_{n-3}+ b_{n-2}+ b_{n-1}, \ n\geq 4.
$$ 
