I have been trying and struggling to come up with a generalized recurrence relation for the number of $L$-bit strings with no runs of $w$ consecutive zeros. I have a relation that gives the right answers for $L = 3$ but it gives the wrong answers for $L = 4$.
I'll use 3-bit strings for a concise example. The 3-bit strings are:
000 001 010 100 101 110 011 111
If $w = 1$, i.e. valid bitstrings have no $0^{1}$, then obviously the only valid bitstring is the one with no zeros at all:
000 001 010 100 101 110 011 111
^^^
1 valid string
If $w = 2$, i.e. valid bitstrings have no $0^{2}$, we can see that 5 bitstrings meet the restriction:
000 001 010 100 101 110 011 111
^^^ ^^^ ^^^ ^^^ ^^^
5 valid strings
If $w = 3$:
000 001 101 100 101 110 011 111
^^^ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^
7 valid strings
And if $w = 4$, obviously all bitstrings are valid, because a run of $0^{4}$ isn't possible with 3-bit strings:
000 001 101 100 101 110 011 111
^^^ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^ ^^^
8 valid strings
After a bunch of reading, I arrived at a piecewise-defined recurrence relation that does give the right values for $L = 3$:
$$ F(L, w) = \begin{cases} 1 & \text{if } w = 1\\ 2^L & \text{if } L < w \\ 2^L - 1 & \text{if } L = w \\ F(L-1, w) + F(L-w, w) & \text{otherwise} \end{cases} $$
I am not convinced that all three base cases are really necessary. I am, however, convinced that the recurrence is not quite right. But, implementing this function programmatically is trivial, so I wrote a Python function that follows this definition and indeed it correctly yields:
F(3, 1) = 1
F(3, 2) = 5
F(3, 3) = 7
F(3, 4) = 8
I realize that three of those cases are hardcoded into the definition, but F(3, 2), the case that invokes the recurrence, does give 5 as I expect it to.
The problem I'm having is that when I run through the values for $L = 4$ (that is, 4-bit strings), I don't get the answers I expect. The hardcoded pieces stay correct, of course, but the values computed by triggering the recurrence are wrong. Clearly, there's something wrong with the relation I've arrived at but I just can't wrap my head around how to get this generalized to any $L$ and any $0^{w}$.
Is anyone able to point out the problem with my recurrence? Or suggest a different mechanism to compute the number of $L$-bit strings that have no $0^{w}$?
Really appreciate any advice on this! I hope what I have is at least going down the right path.
Fix a positive integer $w$.
For nonnegative integers $n,k$ with $k\le w$, let $f(n,k)$ be the number of $n$-bit strings with no run of $w$ consecutive $0$ bits, given an immediately preceding run of exactly $k$ consecutive $0$ bits.
Then we have the recursion $$ f(n,k) = \begin{cases} 0&\text{if}\;\,k=w\\[4pt] 2^n&\text{if}\;\,k+n<w\\[4pt] f(n-1,0)+f(n-1,k+1)\;\;&\text{otherwise}\\ \end{cases} $$ and then, expressed in terms of $f$, the number of $L$-bit strings with no run of $w$ consecutive $0$ bits is just $f(L,0)$.