Number of bit strings of length 8 that do not contain "$100$"? I am thinking the total number of possible strings is $2^8$ and the number of strings with $100$ at the beginning would be $2^8 - 2^3 = 2^5$. Now "$100$" can shift across the string $5$ times going to the right. Is the answer then $2^8 - 2^5 \times 5$? 

A nice technique is the so-called Goulden-Jackson Cluster Method which is a convenient method to derive a generating function for problems of this kind.

We consider words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1\}$$ and the set $\mathcal{B}=\{100\}$ of bad words which are not allowed to be part of the words we are looking for.
We derive a function $F(x)$ with the coefficient of $x^n$ being  the number of wanted words of length $n$.
  According to the paper (p.7) the generating function $F(x)$  is
  \begin{align*}
F(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})}
\end{align*}
  with $d=|\mathcal{V}|=2$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with
  \begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[100])
\end{align*}
We calculate according to the paper
  \begin{align*}
\text{weight}(\mathcal{C}[100])&=-x^3
\end{align*}

It follows:

A generating function $F(x)$ for the number of words built from $\{0,1\}$ which do not contain the subword $100$ is
  \begin{align*}
F(x)&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\
&=\frac{1}{1-2x+x^3}\\
&=1+2x+4x^2+7x^3+12x^4+20x^5\\
&\qquad+33x^6+54x^7+88x^8+143x^9+232x^{10}+\cdots\tag{1}
\end{align*}
The last line (1) was calculated with Wolfram Alpha and we see the coefficient of $x^8$ is $88$.

We conclude: out of $2^8=256$ binary strings of length $8$ there are precisely $88$ words which do not contain the substring $100$.

Of course, we can also calculate the result by hand by expanding the generating function as geometric series and extracting the coefficient of $x^8$.
In order to do so its convenient to use the coefficient of operator $[x^j]$ to denote the coefficient of $x^j$ of a series.
We obtain
  \begin{align*}
[x^8]\frac{1}{1-2x+x^3}&=[x^8]\sum_{n=0}^\infty(2x-x^3)^n\tag{2}\\
&=[x^8]\sum_{n=0}^\infty x^n\sum_{j=0}^n\binom{n}{j}(-x^2)^j2^{n-j}\tag{3}\\
&=\sum_{n=0}^8[x^{8-n}]\sum_{j=0}^n\binom{n}{j}(-1)^j2^{n-j}x^{2j}\tag{4}\\
&=\binom{4}{2}(-1)^22^{4-2}+\binom{6}{1}(-1)^12^{6-1}+\binom{8}{0}(-1)^02^{8-0}\tag{5}\\
&=6\cdot 4-6\cdot 32+1\cdot 256\\
&=88
\end{align*}
  and the claim follows.

Comment:


*

*In (2) we expand the geometric series.

*In (3) we factor out $x^n$ and expand the binom using the formula $$(a-b)^n=\sum_{j=0}^n\binom{n}{j}(-b)^ja^{n-j}$$

*In (4) we use the linearity of the coefficient of operator and apply the formula $$[x^p]x^qA(x)=[x^{p-q}]A(x)$$ Since the exponent of $x^{8-n}$ is non-negative we restrict the upper limit of the sum with $8$.

*In (5) we select the coefficients of $x^{8-n}$. Since $0\leq j\leq n$ and the exponent of $x^{2j}$ is even, we need only to consider $n\in\{4,6,8\}$.
