Use of principle of inclusion and exclusion in counting Here is the question
Q:- How many bit strings of length 8 contain three consecutive zeros?

I tried to solve this by making the cases that three consecutive zeros start from bit number 1, 2 and so on. I approached to my answer correctly. I obtained 107 as my answer.
But I am confused about, how can I solve this question using inclusion-exclusioin principle? Can anyone help me with this? 
 A: As N. F. Taussig shows, Inclusion-Exclusion is not easy to apply to this problem. One other method that can be used is generating functions. To count the number of strings with no more than two zeros in succession, we will represent the atomic strings
$$
\begin{array}{}
1&x\\
10&x^2\\
100&x^3
\end{array}\tag1
$$
Since the atomic strings in $(1)$ can only represent strings that start with a one, we need to also represent $0$-$2$ zeros at the start with 
$$
\begin{array}{}
-&1\\
0&x\\
00&x^2
\end{array}\tag2
$$
Using $(2)$ once and $(1)$ as many times as needed, we get the generating function
$$
\begin{align}
\left(1+x+x^2\right)\color{#090}{\sum_{k=0}^\infty\left(x+x^2+x^3\right)^k}
&=\frac{1+x+x^2}{\color{#090}{1-x-x^2-x^3}}\\
&=\left(1+x+x^2\right)\color{#090}{\left(1+x+2x^2+\dots\right)}\\[6pt]
&=1+2x+4x^2+\dots\tag3
\end{align}
$$
where the denominator $1-x-x^2-x^3$ says that the coefficients of the generating function, for $n\ge3$, obey the recurrence
$$
a_n=a_{n-1}+a_{n-2}+a_{n-3}\tag4
$$
Note that $(4)$ is the same recursion that N. F. Taussig got in their answer.
Using $(4)$, we can extend $(3)$ as far as we want:
$$
\begin{align}
\frac{1+x+x^2}{1-x-x^2-x^3}
&=1+2x+4x^2+7x^3+13x^4+24x^5+44x^6\\
&+81x^7+\color{#C00}{149}x^8+274x^9+504x^{10}+\dots\tag5
\end{align}
$$
$(5)$ says that the number of strings of length $8$ with no more than two zeros in succession is $149$. Since there are $256$ strings of length $8$, we get that there are $256-149=107$ strings of length $8$ with at least $3$ zeros in succession.
A: Let $X\in\{0,1\}. $First we start with the string $000XXXXX \quad (1)$.
Here we have $2^5$ ways. For the next sequence we move the block $000$ on position to the right. To avoid double counting strings starting with $0$ the string starts with 1: 
$1000XXXX \quad (2)\Rightarrow 2^4 \quad (2)$.
Moving the block $000$ one position to the right again. The first position can be 0 or 1: 
$X1000XXX \quad (3)\Rightarrow 2^4 $. 
Similar reasoning for the next 3 strings.
$XX1000XX \quad (4)\Rightarrow 2^4 $
$XXX1000X \quad (5)\Rightarrow 2^4 $
$XXXX1000 \quad (6)\Rightarrow 2^4 $
Now we compare all the strings if there is still double counting. Equal strings are at
$(1), (5): 00010000$
$(1), (5): 00010001$
$(1), (6): 00001000$
$(1), (6): 00011000$
$(2), (6): 10001000$
Therefore we have $2^5+2^4+2^4+2^4+2^4+2^4-5=32+5\cdot 16-5=107$ bit strings of length 8 contain three consecutive zeros. This matches your proposed result.
