Number of binary strings of length $n$, where every $1$, if any, is followed by at most $k$ $0$s 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.
 A: 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.
A: 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.
