Number of bit strings with 3 consecutive zeros or 4 consecutive 1s

Here's one way to get the 107 and the 48 in the comment by mjqxxxx.

Let $a_n$ be the number of bit-strings of length $n$ with 3 consecutive zeros. Then $$a_n=2a_{n-1}+2^{n-4}-a_{n-4}$$ because you can get such a string from a such a string of length $n-1$ by putting a zero or a one at the end, or from a string of length $n-4$ with no 3 consecutive zeros by tacking 1000 on at the end. Clearly $a_0=a_1=a_2=0$ and $a_3=1$, and then you can use the recursion to find $a_4=3$, $a_5=8$, $a_6=20$, $a_7=47$, $a_8=107$.

For bit-strings with 4 consecutive ones, the same logic gets you to $$b_n=2b_{n-1}+2^{n-5}-b_{n-5}$$ and then you proceed as before.

You've left out accounting for strings that have two triple zeroes. So $00010000,00010001,00001000,00011000,10001000$ were added to your total twice. This didn't cause any problems in your count of strings with four $1$s, however, since we can't put four $1$s in two separated places in an $8$-bit string. So the union now has $155$ elements, and cutting out the two duplicates from each symmetry of your intersection calculation turns that to $8$, for a total $107+48-8=147$.

$ \begin{array}{|l|r|l|} \hline format & N & exceptions \\ \hline 000***** & 32 & \\ 1000**** & 16 & \\ *1000*** & 16 & \\ **1000** & 16 & \\ ***1000* & 14 & 0001000* \\ ****1000 & 13 & 000*1000 , 10001000 \\ 1111**** & 13 & 1111000* , 11111000 \\ 01111*** & 7 & 01111000 \\ *01111** & 8 & \\ **01111* & 6 & 0001111* \\ ***01111 & 6 & *0001111 \\ \hline \end{array}$

Total: $147$