Finding a formula for the number of $0$-$1$ sequences of length $n$ having a $0$ in any consecutive $m$ digits

Question

Let $m, n$ be positive integers. Let $S(n,m)$ be the number of sequences of length $n$ and consisting of $0$ and $1$ in which there exists a $0$ in any consecutive $m$ digits. Find a formula for $S(n,m)$.

Let $P(n,m)$ denote the number of strings in which there exists at least one block of $m$ consecutive $1$'s. We have $S(n,m)=2^{n}-P(n,m)$.

Let $P_i(n,m)$ denote the number of strings in which there exists at least one block of $m$ consecutive $1$'s from left starting from the $(i+1)$'th position and ending in the $(i+m)$'th position, with no blocks of $m$ $1$'s starting before the $i+1$'th position. We shall have: $$P(n,m)=\sum_{i=0}^{n-m-1}{P_i(n,m)}$$

We shall first count $P_i(n,m)$. From the $1$'st position to the $i-1$'th position there are $S(i-1,m)$ ways to choose $1$'s and $0$'s. The $i$'th position must be $0$, and from the $i+1$'th to the $i+m$'th position, there must be $m$ number $1$'s. From the $i+m+1$'th position to the $n$'th position, we can choose either $1$ or $0$, there are $2^{n-m-i}$ ways to choose. Therefore: $$P_i(n,m)=2^{n-m-i}S(i-1,m)=2^{n-m-1}-2^{n-i-m}P(i-1,m)$$

Thus $$P(n,m)=(n-m+1)2^{n-m-1}-\sum_{i=0}^{n-m}{2^{n-m-i}P(i-1,m)}$$ with $P(-1,m)=1$.

Here I am stuck. How can I progress ? Or is there a better way to find a general formula for $S(n,m)$ ? Do such formula exist?

(Please let me know if this question should be closed. Sorry for my English grammar)

Answer 1

I don't think that there is an easy closed formula for $S(n,m)$, but it should satisfy the following linear recurrence for $n>m>0$ $$S(n,m)=\sum_{k=1}^m S(n-k,m).$$ because in the last part of the sequence we may have $0$, $01$, $011$, $\dots$, $0\underbrace{1\dots 1}_{m-1}$.

Moreover $S(n,1)=1$, $S(n,2)=F_{n+2}$ where $F_k$ is the $k$-th Fibonacci number, $S(n,3)=F^{(3)}_{n+3}$ where $F^{(3)}_{k}$ is the $k$-th Tribonacci number, $S(n,4)=F^{(4)}_{n+4}$ where $F^{(4)}_{k}$ is the $k$-th Tetranacci number,

Answer 2

Let $S(n,m)$ be the number of sequences of length $n$ and consisting of $0$ and $1$ in which there exists a $0$ in any consecutive $m$ digits.

Current thought process, needs improvement:

Note that, $\#$ ways to choose a continuous block of size $m$ from a binary string of length $n$ is $${n-m+1 \choose {1}} =\ (n-m+1)$$ Assume that you have chosen a random $m$-sized continuous block in a binary string of length $n$. Number of ways that this $m$-sized block will have $\color{red}{\text{at least}}$ one zero is $\ (2^m-1)$, since we are only excluding the case where all entries are $1$s.

Previous though process, needs improvement:

Let $P(n,m)$ denote the number of strings in which there exists at least one block of $m$ consecutive $1$'s. Then we can write, $$S(n,m)=2^{n}-P(n,m)$$ We start computing $P(n,m)$. Let, $P(n,m)$ counts the sequences which comprise a set $A$. Then any element in $A$ will be of the form $$a_n = \underbrace{\color{blue}{*\dots*} \underbrace{\color{red}{11\dots 1}}_{m} \color{blue}{*\dots*}}_{n}$$ If we take that consecutive sequence of $1$s as a single block, then $P(n,m)$ becomes ${n-m+1 \choose \color{red}{1}}\ \color{blue}{2^{n-m}}$ , since the rest of the terms in the binary sequence can be anything. $$\therefore S(n,m) = 2^n - P(n,m) = 2^n - {n-m+1 \choose 1}\ 2^{n-m} \\ = 2^n - (n-m+1)\ 2^{n-m} \\ = \fbox{$2^{n-m}\ (2^m -n +m -1)$}$$