Number of bit strings of length 8 that do not contain "$100$"?

As discussed in the comments, the straight forward approach as proposed in the question won't work because it multiply counts the bad strings in which $100$ appears more than once (indeed, it counts bad strings once for each appearance of $100$).

For short strings (like length $8$) a more careful count via the principle of Inclusion/Exclusion isn't impossible but it's not exactly easy and, as the length increases, this method gets harder and harder. I think it's easier to attack the problem recursively. Toward that end, define some sub-types of the "good" strings of length $n$. Specifically, let $A_n$ denote those good strings that end in $1$ and let $B_n$ denote those that end in $10$. Note that the total $T_n$ is then given by $$T_n=A_n+B_n+1$$ where the $1$ comes from the good string $0^n$ which ends in neither $1$ nor $10$.

Recursive, we note that $$A_n=A_{n-1}+B_{n-1}+1=T_{n-1}$$ since you get a good string of length $n$ by appending a $1$ to any good string of length $n-1$. Similarly $$B_n=A_{n-1}=T_{n-2}$$ Thus $$T_n=T_{n-1}+T_{n-2}+1$$

It is easy to see that $A_1=1$, $A_2=2$, $B_1=0$, $B_2=1$ whence $$\{T_n\}=\{2,4,7,12,20,33,54,88,\cdots\}$$

Consistency Check: Let's count $T_4,\;T_5,\;T_6$ directly. There are $16$ strings of length $4$ and the bad ones are $x100$ and $100x$, thus there are $4$ bad strings so $T_4=16-4=12$ as desired. Similarly the bad strings of length $5$ are $100xx$, $x100x$, $xx100$ so $T_5=32-12=20$ as desired. To count the bad strings of length $6$ we have to be a little careful...the patterns are $100xxx$, $x100xx$, $xx100x$, $xxx100$ but we have to add back $1$ for the double counted string $100100$. Thus $T_6=64-8\times 4+1=33$ as desired.

Induction shows that, in fact, $T_n=F_{n+3}-1$ where $F_i$ denotes the Fibonacci numbers $\{F_i\}_{i=1}^{\infty}=\{1,1,2,3,5,8,13,21,\cdots\}$

Using generating functions with $z$ for zero and $w$ for ones we get the generating function

$$(1+z+z^2+\cdots) \left(\sum_{q\ge 0} ((w+w^2+w^3+\cdots) z)^q\right) (1+w+w^2+\cdots).$$

This yields

$$\frac{1}{1-z}\left(\sum_{q\ge 0} z^q \frac{w^q}{(1-w)^q}\right) \frac{1}{1-w} \\ = \frac{1}{1-z}\frac{1}{1-w} \frac{1}{1-wz/(1-w)} \\ = \frac{1}{1-z} \frac{1}{1-w-wz}.$$

As we are only interested in the count we may drop the distinction between zeros and ones, getting

$$\frac{1}{1-z} \frac{1}{1-z-z^2} = \frac{2+z}{1-z-z^2} - \frac{1}{1-z}.$$

Extracting coeffcients from this yields in terms of Fibonacci numbers

$$2F_{n+1} + F_n - 1 = F_{n+1} + F_{n+2} - 1 = F_{n+3} - 1.$$

We can confirm these results using the DFA method which yields

> GFNC([[1,0,0]], 2,true);
                                   [[1, 0, 0]]

                                   Q[], 0, Q[]

                                  Q[], 1, Q[1]

                                Q[1], 0, Q[1, 0]

                                  Q[1], 1, Q[1]

                             Q[1, 0], 0, Q[1, 0, 0]

                                Q[1, 0], 1, Q[1]

                            Q[1, 0, 0], 0, Q[1, 0, 0]

                            Q[1, 0, 0], 1, Q[1, 0, 0]

                                       1
                              --------------------
                                        2
                              (z - 1) (z  + z - 1)

This link includes an explanation of the Goulden-Jackson cluster method by @MarkusScheuer.

Using inclusion-exclusion we have for the location of the forbidden pattern when $n=8$ the possibilities $(1),(2),(3),\ldots,(6)$ and $(1,4),(2,5),(3,6)$ and $(1,5),(2,6)$ and $(1,6).$ We thus obtain

$$2^8 - 6\times 2^5 + 6\times 2^2 = 88.$$

We can generalize the inclusion-exclusion argument. Suppose we have $q$ instances of the pattern where $q\le\lfloor n/3\rfloor.$ This leaves $n-3q$ free slots that must be distributed in the $q+1$ spaces between / surrounding the patterns. By stars and bars this can be done in the following number of ways:

$${n-3q+q\choose q} = {n-2q\choose q}.$$

We thus obtain by inclusion-exclusion the closed form

$$\sum_{q=0}^{\lfloor n/3\rfloor} {n-2q\choose q} (-1)^q 2^{n-3q}.$$

We can evaluate this with the Egorychev method. Introduce

$${n-2q\choose q} = {n-2q\choose n-3q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-3q+1}} (1+z)^{n-2q} \; dz.$$

Observe that this vanishes when $3q\gt n$ so we may extend the range of $q$ to infinity, getting for the sum

$$\frac{2^n}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} \sum_{q\ge 0} \frac{z^{3q}}{(1+z)^{2q}} (-1)^q 2^{-3q} \; dz \\ = \frac{2^n}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} \frac{1}{1+2^{-3}z^3/(1+z)^2} \; dz \\ = \frac{2^n}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n+2} \frac{1}{1+2z+z^2+2^{-3}z^3} \; dz.$$

Now put $z/(1+z) = w$ so that $z = w/(1-w)$ and $1+z = 1/(1-w)$ and $dz = 1/(1-w)^2 \; dw$ and

$$1+2z+z^2+2^{-3}z^3 = \frac{1}{8} \frac{(w-2)(w^2+2w-4)}{(1-w)^3}$$

which yields for the integral

$$\frac{2^n}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{8(1-w)^3}{(w-2)(w^2+2w-4)} \frac{1}{(1-w)^2} \; dw \\ = \frac{2^n}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{8}{(w-2)(w^2+2w-4)} \; dw.$$

This is

$$2^n [w^n] \frac{8}{(w-2)(w^2+2w-4)} = [w^n] \frac{8}{(2w-2)(4w^2+4w-4)} \\ = [w^n] \frac{1}{(w-1)(w^2+w-1)} \\ = [w^n] \frac{1}{(1-w)(1-w-w^2)}.$$

This is the same generating function as what we obtained earlier and the argument is concluded.

Addendum. Wilf also succeeds here. We have the generating function

$$\sum_{n\ge 0} z^n 2^n \sum_{q=0}^{\lfloor n/3\rfloor} {n-2q\choose n-3q} (-1)^q 2^{-3q} = \sum_{q\ge 0} 2^{-3q} (-1)^q \sum_{n\ge 3q} z^n 2^n {n-2q\choose n-3q} \\ = \sum_{q\ge 0} 2^{-3q} (-1)^q \sum_{n\ge 0} z^{n+3q} 2^{n+3q} {n+q\choose n} = \sum_{q\ge 0} z^{3q} (-1)^q \sum_{n\ge 0} z^{n} 2^{n} {n+q\choose n} \\ = \sum_{q\ge 0} z^{3q} (-1)^q \frac{1}{(1-2z)^{q+1}} = \frac{1}{1-2z} \frac{1}{1+z^3/(1-2z)} \\ = \frac{1}{1-2z+z^3}.$$

This is the same generating function as before, done.