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.
Best Answer
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 $n\le 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-2}\tag{$n>k+2$} $$ Subtracting these equations $$ \boxed{a_{n}=2a_{n-1}-a_{n-k-2}.} $$
You can compute $a_n$ in $O(k^3\log n)$ time if you are careful. The last recurrence can be written as a matrix equation, which I illustrate when $k=2$: $$ \begin{bmatrix}a_n \\ a_{n-1} \\ a_{n-2} \\a_{n-3}\end{bmatrix}= \begin{bmatrix} 2 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} a_{n-1} \\ a_{n-2} \\a_{n-3}\\a_{n-4}\end{bmatrix} $$ Letting $A$ be the $(k+2)\times (k+2)$ matrix, iterating the recurrence implies $$ \begin{bmatrix}a_n \\ a_{n-1} \\ \vdots \\a_{n-k-1}\end{bmatrix}=A^{n-k-2}\begin{bmatrix}a_{k+2} \\ a_{k+1} \\ \vdots \\a_{1}\end{bmatrix} $$ 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.