Vtyjkyuk

This question is similar to the one asked here by another user, but I want to ask it again since it was worded poorly there and not enough context was provided.

Actually, this question was asked as a coding problem in a placement test (which is over now of course), where the input is given as two numbers $n$ and $k$, and we have to output the number of binary strings of length $n$, where every $1$ in the binary string, if any exists, is followed by at most $k$ zeroes.

For eg. for $n = 5, k = 0$, output must be $6$, which is the set $(00000, 00001, 00011, 00111, 01111, 11111)$.

I believe this can be done using dynamic programming, by developing a recurrence relation between a larger problem instance $f(n, k)$ and smaller ones, for eg. $f(n, k-1), f(n-1, k-1)$ etc., but I haven't been able to find one.

Base cases are easy to see: $f(n, 0) = n + 1$ $forall n$, $f(0, k) = 0$ $forall k$; and $f (n , k) = 2^n$ for $k geq n - 1$

Solution for a non-trivial instance - $f(6, 2) = 52$

Edit: I realized that Mike Earnest has found a solution in the linked question, based on combinatorics, so I am only interested in a recurrence relation. Also, from an algorithmic point of view, the time complexity of computing $n choose k$ is much higher than a polynomial solution that can be found with a recurrence relation, by building bottom-up from the base cases.

Let $a_n$ be the number of strings of length $n$ where every $1$ is followed by at most $k$ zeroes. There are two cases; either the string has a one, or it doesn't. In the former case, the maximal run of zeroes at the end must be of length at most $k$. Therefore, for all $n>k+1$,
$$
a_n = 1+a_n-1+a_n-2+dots+a_n-k-1
$$
As you said, the base cases are $a_n=2^n$ for $nle k+1$. (Note the base case $a_0=1$, because there is one valid string of length $0$, namely the empty string).

For example, when $k=0$, the recurrence is $a_n=a_n-1+1$, which implies $a_n=n+1$. Also,
$$
f(4,2) = 1+f(3,2) + f(2,2) + f(1,2) =1+8 + 4 + 2 = 15\
f(5,2) = 1+f(4,2) + f(3,2) + f(2,2) =1+15+8+4= 28\
f(6,2) = 1+f(5,2) + f(4,2) + f(3,2) =1+28+15+8= 52
$$

You can even simplify this recurrence a bit more. The recurrence when $n$ is replaced with $n-1$ is
$$
a_n-1 = 1+a_n-2+a_n-3+dots+a_n-k-2tag$n>k+2$
$$
Subtracting these equations
$$
boxeda_n=2a_n-1-a_n-k-2.
$$

You can compute $a_n$ in $O(k^3log n)$ time if you are careful. The last recurrence can be written as a matrix equation, which I illustrate when $k=2$:
$$
beginbmatrixa_n \ a_n-1 \ a_n-2 \a_n-3endbmatrix=
beginbmatrix 2 & 0 & 0 & -1 \ 1 & 0 & 0 & 0 \0 & 1 & 0 & 0 \0 & 0 & 1 & 0 endbmatrix
beginbmatrix a_n-1 \ a_n-2 \a_n-3\a_n-4endbmatrix
$$
Letting $A$ be the $(k+2)times (k+2)$ matrix, iterating the recurrence implies
$$
beginbmatrixa_n \ a_n-1 \ vdots \a_n-k-1endbmatrix=A^n-k-2beginbmatrixa_k+2 \ a_k+1 \ vdots \a_1endbmatrix
$$
Therefore, you can compute the vector on the left by computing a power of the matrix $A$. Using exponentiation by squaring, this takes only $O(log n)$ matrix multiplication, each of which naively takes $O(k^3)$ arithmetic operations.

Let $f(n)$ denote the number of valid strings of length which end with $1$.
Base case $f(0)$ shall be equal to $1$.

$$f(n)= sum_i=0^k+1 f(n-i)$$

Now the final answer shall be the sum of all $f(i)$'s, i.e ans$ = sum_i=0^n f(i)$.
The given algorithm would take quadratic time. To enhance it further we can use a prefix array to store sums of previously calculated subproblems so that the RHS can be computed in constant time.