Finding a combinatorial recurrence relation with three variables This question is from the generating functionology textbook,
Let $f(n, m,k)$ be the number of strings of n $0$’s and $1$’s that contain
exactly $m$ $1$’s, no $k$ of which are consecutive.
Find a recurrence formula for $f$. It should have $f(n, m,k)$
on the left side, and exactly three terms on the right.
There were previous examples involving binomial coefficients and partitions, so I am sure the method of finding the recurrence is similar (splitting the total into piles with n and without n etc)
This just seems on another level of complexity, any help would be much appreciated.
 A: Imagine that you build such a binary string by appending $0$ or $1$ to a string one shorter.  The difficulty, of course, is that you can't be sure you can safely add another $1$ as you might violate the "consecutive condition".  Thus, you need to keep track of the possible endings.  Accordingly, define $f(n,m,k,i)$ to be the number of "good" strings that end in exactly $i$ $1's$. Of course we can rewrite this function in terms of the original one...we know that the strings it counts end in $01^{i}$ but what comes before can end in either digit, has exactly $m-i$  $1's$ and still satisfies the consecutive condition.  Hence $$f(n,m,k,i)=f(n-i-1,m-i,k)$$ Returning to the problem, we immediately get the recursion:  $$f(n,m,k)=f(n-1,m,k)+f(n-1,m-1,k)-f(n-1,m-1,k,k-1)$$  Where the first term comes by appending a $0$, the second by appending a $1$ and the third by removing those strings which would violate the consecutive condition.  Finally, then, we get,
$$f(n,m,k)=f(n-1,m,k)+f(n-1,m-1,k)-f(n-1 -(k-1)- 1,m-1-(k-1),k)=f(n-1,m,k)+f(n-1,m-1,k)-f(n-k-1,m-k,k)$$
Note:  this seems like a good candidate for a "fencepost" type error.  That is, I would not be surprised if some indices were off by $1$. I'd check it carefully for reasonably small figures.
A: We can break down $f(n,m,k)$ into how many consecutive ones it ends with
$$
f(n,m,k)=\left\{\begin{array}{}
0&\text{if }m<0\text{ or }n<m&\text{impossible}\\[9pt]
[n<k]&\text{if }n=m&\text{only ones}\\
\displaystyle\sum_{j=0}^{k-1}f(n-j-1,m-j,k)&\text{if }n\gt m&\begin{array}{l}\text{ends with a zero}\\[-4pt]\text{and $j$ ones}\end{array}
\end{array}\right.
$$
where $[\cdots]$ are Iverson Brackets.
Here is a table for $k=3$:
$$
\begin{array}{r|rr}
&0&1&2&3&4&5&6&7&8&9&n\\\hline
0&1&1&1&1&1&1&1&1&1&1\\
1&0&1&2&3&4&5&6&7&8&9\\
2&0&0&1&3&6&10&15&21&28&36\\
3&0&0&0&0&2&7&16&30&50&77\\
4&0&0&0&0&0&1&6&19&45&90\\
5&0&0&0&0&0&0&0&3&16&51\\
6&0&0&0&0&0&0&0&0&1&10\\
7&0&0&0&0&0&0&0&0&0&0\\
m
\end{array}
$$
