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.
(a) Find a recurrence formula for $f$. It should have $f(n, m, k)$ on the left side, and exactly three terms on the right.
My attempted answer is as follows (I am not sure if this is correct):
$$f(n,m,k) = f(n-1,m,k) + f(n-1,m-1,k) - f(n-k,m-k,k)$$
The reasoning is: counting the number of strings with $0$ as the last entry, plus the number of strings with $1$ as the last entry, minus the number of strings ending in $k$ $1$'s.
I am not sure how to start (b) or (c): (b) Find in simplest form the generating functions $$F_k(x,y) = \sum_{n,m \geq 0}f(n,m,k)x^ny^m$$
(c) Find an explicit formula for $f(n,m,k)$ from the generating function (this should involve only a single summation, of an expression that involves a few factorials).