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$.
Here's an alternate way of solving your question.
Let $a_n$ be the number of bit strings of length $n$ containing a pair of consecutive $1$'s.
In order to construct such a bit string, one could start with
- $0$ and follow with a string of length $(n-1)$ containing a pair of consecutive $1$'s
- $10$ and follow with a string of length $(n-2)$ containing a pair of consecutive $1$'s
- $11$ and follow with any string of length $(n-2)$
Since these three cases are mutually exclusive and exhaust the possibilities for how such a string might start, we can apply the sum rule and write down the following recurrence relation valid for all $n \ge 2;$
$a_n = a_{n-1} + a_{n-2} + 2^{n-2}$
(Recall that there are $2^k$ bit strings on length $k$).
Now for the initial conditions:
Best Answer
You are saying (correctly) that the number you are looking for is $2^8-B$ where $B$ is the number of bad strings, i.e., those containing six consecutive zeros. And to know what $B$ is you say correctly that it is the sum $B_6+B_7+B_8$, where $B_k$ is the number of $8$-bit strings containing $k$ consecutive zeros. Now, what is $B_8$ (hint: that is very easy to answer). What is $B_7$ (hint: not a large number at all, you can list all such strings). What is $B_6$ (hint: a slightly bigger number, but do you notice some symmetry?)