<s>[INST] 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.
 [/INST] 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}
$$
</s>