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?
Best Answer
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$.