Number of bit strings of length four do not have two consecutive 1s I came across following problem:

How many bit strings of length four do not have two consecutive 1s?

I solved it as follows:

Total number of bit strings of length: $2^4$
  Total number of length 4 bit strings with 4 consecutive 1s: 1
  Total positions for three consecutive 1s in length 4 bit string: 2 (111X, X111)
  Number of bit strings for each of above positions: 2 (X can be 0 or 1)
  Total positions for two consecutive 1s in length 4 bit string: 3 (11XX, X11X, XX11)
  Number of bit strings for each of above positions: 4
  By inclusion exlcusion principle, the desired count $=2^4-3\times 4+2\times 2-1=16-12+4-1=7$

However the correct solution turns out to be 8. It seems that I incorrectly applied inclusion exclusion principle. Where did I go wrong?
 A: Inclusion-Exclusion to Count Bad Strings
To count the number of bit strings with $2$ consecutive one bits (bad strings), I would let
$$
\begin{align}
S_1&=11xx&4\\
S_2&=x11x&4\\
S_3&=xx11&4\\
N_1&=&12
\end{align}
$$
Then
$$
\begin{align}
S_1\cap S_2&=111x&2\\
S_1\cap S_3&=1111&1\\
S_2\cap S_3&=x111&2\\
N_2&=&5
\end{align}
$$
and
$$
\begin{aligned}
S_1\cap S_2\cap S_3&=1111&1\\
N_3&=&1
\end{aligned}
$$
The count of bad strings is $N_1-N_2+N_3=8$.
The count of good strings is $16-8=8$.

Generating Functions
Let $x$ represent the atom '$0$' and $x^2$ represent the atom '$10$' and build all possible strings by concatenating one or more atoms and removing the rightmost '$0$'.
$$
\begin{align}
\overbrace{\vphantom{\frac1x}\ \ \ \left[x^4\right]\ \ \ }^{\substack{\text{strings of}\\\text{length $4$}}}\overbrace{\ \quad\frac1x\ \quad}^{\substack{\text{remove the}\\\text{rightmost '$0$'}}}\sum_{k=1}^\infty\overbrace{\vphantom{\frac1x}\left(x+x^2\right)^k}^\text{$k$ atoms}
&=\left[x^4\right]\frac{1+x}{1-x-x^2}\\
&=\left[x^4\right]\left(1+2x+3x^2+5x^3+8x^4+13x^5+\dots\right)\\[9pt]
&=8
\end{align}
$$
Note that the denominator of $1-x-x^2$ induces the recurrence $a_n=a_{n-1}+a_{n-2}$ on the coefficients.

Recurrence
Good strings of length $n$ can be of two kinds: a good string of length $n-1$ followed by '$0$' or a good string of length $n-2$ followed by '$01$'. That is,
$$
a_n=a_{n-1}+a_{n-2}
$$
Starting with
$a_0=$ the number of good strings of length $0=1$.
$a_1=$ the number of good strings of length $1=2$.
we get $a_4=8$.
A: If I were doing this by inclusion-exclusion, I'd go: $16$ strings of length four; $12$ with at least one pair of consecutive ones ($11xx,x11x,xx11$ with $x$s arbitrary); five with at least two pair of consecutive ones ($111x,1111,x111$); one with three pair of consecutive ones; so $16-12+5-1=8$. 
