Let’s first count the $15$-bit strings that have exactly $9$ consecutive ones.
If the bit string is $b=b_1b_2\dots b_{15}$, the block of ones can start at $b_1,b_2,b_3,b_4,b_5,b_6$, or $b_7$. If it starts at $b_1$, $b_{10}$ must be $0$, and bits $b_{11}$ through $b_{15}$ can be anything. That’s five bits that can be set arbitrarily to $0$ or $1$; there are $2^5=32$ ways to do that, so there are $2^5$ $15$-bet strings that begin with a string of exactly $9$ consecutive ones. Similarly, there are $2^5$ that end with such a string. If the string of $9$ ones starts at $b_2,b_3,b_4,b_5$, or $b_6$, on the other hand, it must have a $0$ on each end. That accounts for $9+2=11$ bits, leaving only $15-11=4$ bits to be set arbitrarily. In each case this can be done in $2^4=16$ ways. Thus, we get a grand total of $2\cdot2^5+5\cdot2^4=64+80=144$ such bit strings.
There are of course exactly as many that have exactly $9$ consecutive zeroes, and no $15$-bit string can have both, so there are $2\cdot144=288$ $15$-bit strings that contain exactly $9$ consecutive ones or consecutive zeroes.
A string of at least $9$ ones can still begin at any of the first seven positions. If it begins with $b_1$, we must have $b_1=b_2=\ldots= b_9=1$, but the remaining $6$ bits can be set arbitrarily, since we no longer have to require that $b_{10}=0$; this case therefore yields $2^6$ strings. If it begins with one of $b_2$ through $b_7$, it must be preceded by a zero, so a total of ten bits are determined: a zero followed by $9$ ones. The remaining $5$ bits, however, can be set arbitrarily, so these six cases yield another $6\cdot2^5$ strings. And as before we’ll get just as many with a string of at least $9$ zeroes, so the grand total is $2\left(2^6+6\cdot2^5\right)=512$.
Say that a string is good if it contains the substring $10$, and let $a_n$ be the number of good strings of length $n$. There are two ways to get a good string of length $n+1$.
We can start with a good string of length $n$ and append either a $0$ or a $1$; this produces $2a_n$ good strings of length $n+1$, two for each good string of length $n$.
We can append a $0$ to a bad string of length $n$ that ends in $1$. To see how many good strings of length $n+1$ are of this form, we need to count the bad strings of length $n$ that end in $1$. Show that such a string must be of the form $0^k1^{n-k}$, where $0\le k<n$, then count those strings.
You should find that you have a recurrence of the form $a_{n+1}=2a_n+f(n)$ for some simple function $f$. You’ve probably learned some techniques for finding closed forms for such recurrences; if not, or if you’re not sure of them, you might find my answer to this question helpful.
Finally, you can get $a_8$ either by working up through the recurrence — it’s only four steps, since you already know that $a_4=11$ — or from the closed form, once you have it.
Best Answer
Let $a_n$ be a bit string of length n without 000, then it can be
$a_{(n-3)}$ with 100 added at end,
or $a_{(n-2)}$ with 10 added at end,
or $a_{(n-1)}$ with 1 added at end.
So $a_n = a_{(n-1)} +a_{(n-2)} + a_{(n-3)}$
starting with $a_0 = 1, a_1=2, a_2 = 4$
The ending of any successful chain can be categorised as 1(111,101,011,001) 10(110,010) or 100.
1 can be added to any successful chain of length (n-1) no matter what it ended with.
10 can be added to any successful chain of length (n-2) no matter what it ended with.
100 can be added to any successful chain of length (n-3) no matter what it ended with.