Formula for binary sequences of length $m$ with no $n$ consecutive $1$s?
I know The number of binary strings of length $m$ without consecutive $1$s is the Fibonacci number $F_{m+2}$.
But how about no $n$ consecutive $1$s?
Any help will be appreciated! Thank you
The same idea will work to make a recurrence. To make a sequence of length $m$, you can take one of length $m-1$ and add a zero, one of length $m-2$ and add $01$, one of length $m-3$ and add $011$ on up to $m-n$ adding a zero and $n-1\ \ 1$'s