Number of possible bit sequences of length m with at least n consecutive 1's in them I have seen similar questions to this but they each seem to be special cases of this general question. Answering this would be beneficial to my research, but I am not a combinatorics expert, and this seemingly simple question eludes me. Is there a simple formula to calculate this? Everything I have seen online has been centered around things like "either 2 consecutive 1's or 0's" or "contains no ..".
If it helps, I know that for $m = 8$ bits and say the sequence is denoted $S(m,n)$
$$  
S(m = 8, n = 1) = 255 \\  
S(8,2) = 201  \\
S(8,3) = 107  \\
S(8,4) = 48   \\
S(8,5) = 20   \\
S(8,6) = 8   \\
S(8,7) = 3   \\
S(8,8) = 1 
$$
Interestingly I'm finding that $S(8,4)=S(9,5)=S(10,6)=S(11,7)=48$
I haven't tested $S(12,8)$ because I don't want my computer to melt but I'm seeing a pattern... However this does not seem to work for $m<8$.
 A: If the string is $m$ bits long and you demand a run of exactly $n\ 1$s we can find a formula for $n \ge \frac m2$.  Let us call this $T(m,n)$.  If the run is at one end of the string ($2$ choices) you need a $0$ at the end of the run and have $2^{m-n-1}$ choices for the other bits.  If the run is not at the end of the string, there are $m-n-1$ places it can start and you have $2^{m-n-2}$ choices to complete the string.  If $m-n-2$ is negative there are no other bits to fill in. So
$$T(m,n)=\begin {cases} 1&n=m\\2&n+1=m\\2^{m-n}+(m-n-1)2^{m-n-2}&n+2 \le m \end {cases} $$
and the fact that it only depends on $m-n$ is clear.  Then
$$S(m,n)=\sum_{i=n}^mT(m,i)$$
I repeat that this only works for $n \ge \frac m2$.  The reason it only depends on $m-n$ is because if you take a string of the type $(m,n)$ you can find a unique string of type $(m+1,n+1)$ by extending the run by one more bit.
A: Thanks to @Ross Millikan formula, which I searched with Approach Zero, I could find this answer, and using again Approach Zero with that result, this other beautiful answer. Both give the complementary result, so in your case we have:
$$S(m,n) = 2^m-\sum_{q=0}^{\lfloor m/n\rfloor}
{m-nq\choose q} (-1)^q 2^{m-(n+1)q}
+ \sum_{q=0}^{\lfloor m/n\rfloor - 1}
{m-n(q+1)\choose q} (-1)^q 2^{m-n-(n+1)q}$$
See the links for details.
A: I will not give a formula, but just a recurrence relation. Let T(m, n) be the number of strings of length m with a run of n consecutive 1's.
Consider all the strings of length m-1. Exactly T(m-1, n) of them already contain a string of 'n' consecutive digits. Since we can add a 0 or a 1 we will get double this amount of length m strings strings.
However adding a 1 in the m'th place will give a new good string if the last (n-1) digits are a 1 and the n'th to last digit is a 0 and in addition the digits in place 1, ..., m - n - 1 do not contain a run of n consecutive 1's. i.e. the string looks like this:
$$
\underbrace{xx..xx}_{m - n - 1}0\underbrace{11..11}_{n - 1}
$$
There are 2^{m - n - 1} possibilities for the x-digits, but we should exclude T(m - n - 1, n) of them to avoid the double counting.
Adding it all up we find
$$
T(m, n) = 2\cdot T(m - 1, n) - T(m - n - 1, n) + 2^{(m - n - 1)} 
$$
If $m - n - 1 \leq n$, i.e. $m \leq 2n + 1$, the $T(m - n - 1, n)$ term vanishes and you should be able to solve the recurrence relation.
