The following problem is taken from the book generatingfunctionology (P.28) by Herbert S. Wilf.
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.
(b) Find, in simple closed form, the generating functions $$ F_k(x,y)=\sum_{n,m\ge0}f(n,m,k)x^ny^m \,\,\,\,\,\,\,\,\ (k=1,2,...). $$ (c) Find an explicit formula for $f(n,m,k)$ from the genrating function (this should involve only a single summation, of an expression that involves a few factorials).
I was able to solve (a) and (b) and found that the generating functions is $$ F_k = \frac{1-x^ky^k}{1-x-xy-x^{k+1}y^k} $$ However, I cannot seem to be able to extract the sequence from this function. Any help will be appreciated.
Edit:
I've added the way I solved (a) and (b) to allow any criticism in case I got the function wrong. My solution to (a) goes as follows:
Given $m,n,k$ such that $0\le k\le m \le n$ and $k\lt n$, we look at all of the bit string of length $n$ that contain exactly $m$ $1$'s, no $k$ of which are consecutive. We split these strings into two sets. The first composed of all the strings that end with $0$. This set has $f(n-1,m, k)$ strings since by removing the $0$ from the end of the string we obtain a one to one correspondence between the strings in our set and the strings $f(n-1,m, k)$ counts. The other set is composed of all the strings that end with $1$. By removing the last bit we obtain a one to one correspondence between our set and all strings counted by $f(n-1,m-1, k)$, except those that have $k-1$ consecutive $1$'s at the end. To count the latter we first note that since $k\lt n$ there must be another bit, which must be $0$, before the last $k-1$ $\,1$'s. By removing the last $k$ bits ($10\cdots0$) we obtain a one to one correspondence with the strings that are counted by $f(n-k-1,\,m-k,\,k)$. With that we obtain the recursion: $$f(n,m,k) = f(n-1,m,k) + f(n-1,m-1,k) - f(n-k-1,\,m-k,\,k)$$ In addition, we note the if $0\le m \le n$ and $k > m$, then $f(n,m,k) = \binom{n}m$ , since we can't have more consecutive $1$'s than there are $1$'s, so the problem is reduced to counting the number of strings with length $n$ that have $m$ $1$'s. For all other cases we write $f(n,m,k) = 0$ which completes the definition.
To Solve (b) I did the following:
$$ \begin{align} F_k(x,y) & = \sum_{n,m\ge0}f(n,m,k) x^n y^m \\ & = \sum_{n=0}^{\infty}\sum_{m=0}^{n}f(n,m,k) x^n y^m \\ & = \sum_{n=0}^{k-1}\sum_{m=0}^{n}f(n,m,k) x^n y^m + \sum_{n=k}^{\infty}\sum_{m=0}^{k-1}f(n,m,k) x^n y^m + \sum_{n=k}^{\infty}\sum_{m=k}^{n}f(n,m,k) x^n y^m \\ & = \sum_{n=0}^{k-1}\sum_{m=0}^{n}\binom{n}m x^n y^m + \sum_{n=k}^{\infty}\sum_{m=0}^{k-1}\binom{n}m x^n y^m + \sum_{n=k}^{\infty}\sum_{m=k}^{n}f(n,m,k) x^n y^m \end{align} $$ By using the convention that $\binom{n}m = 0$ when $m\gt n$, and noting that when $m=n\ge k$ we have $f(n,m,k)=0$ we can write the above equation as follows: $$ \begin{align} & \sum_{m=0}^{k-1}\sum_{n=0}^{\infty}\binom{n}m x^n y^m + \sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n,m,k) x^n y^m \\ =& \sum_{m=0}^{k-1} \frac{x^m}{(1-x)^{m+1}} y^m + \sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n,m,k) x^n y^m \\ =& \frac{1}{1-x} \cdot \omega(x,y) + \sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n,m,k) x^n y^m \end{align} $$ where: $$\omega(x,y) := \frac{1 - (\frac{xy}{1-x})^k}{1 - \frac{xy}{1-x}}.$$ Using the recusion formula obtained in (a) we can expand the second summand like so: $$ \begin{align} \sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n,m,k) x^n y^m & = A + B - C \end{align} $$ where: $$ \begin{align} A & =\sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n-1,m,k) x^n y^m \\ & = x\sum_{n=k}^{\infty}\sum_{m=k}^{n}f(n,m,k) x^n y^m \\ & = x\left(\sum_{n=0}^{\infty}\sum_{m=0}^{n}f(n,m,k) x^n y^m - \sum_{n=0}^{k-1}\sum_{m=0}^{n}f(n,m,k) x^n y^m - \sum_{n=k}^{\infty}\sum_{m=0}^{k-1}f(n,m,k) x^n y^m \right)\\ & = x\left(F_k(x,y) - \sum_{n=0}^{k-1}\sum_{m=0}^{n}\binom{n}m x^n y^m - \sum_{n=k}^{\infty}\sum_{m=0}^{k-1}\binom{n}m x^n y^m \right)\\ & = x\left(F_k(x,y) - \sum_{m=0}^{k-1}\sum_{n=0}^{\infty}\binom{n}m x^n y^m\right)\\ & = xF_k(x,y) - \frac{x}{1-x} \cdot \omega(x,y)\\ \\ B & =\sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n-1,m-1,k) x^n y^m \\ & = xy\sum_{n=k}^{\infty}\sum_{m=k-1}^{n-1}f(n,m,k) x^n y^m \\ & = xy\left(\sum_{n=0}^{\infty}\sum_{m=0}^{n}f(n,m,k) x^n y^m - \sum_{n=0}^{k-1}\sum_{m=0}^{n}f(n,m,k) x^n y^m - \sum_{n=k}^{\infty}\sum_{m=0}^{k-2}f(n,m,k) x^n y^m \right)\\ & = xy\left(F_k(x,y) - \sum_{n=0}^{k-1}\sum_{m=0}^{n}\binom{n}m x^n y^m - \sum_{n=k}^{\infty}\sum_{m=0}^{k-2}\binom{n}m x^n y^m \right)\\ & = xy\left(F_k(x,y) - \sum_{m=0}^{k-2}\sum_{n=0}^{\infty}\binom{n}m x^n y^m - x^{k-1}y^{k-1}\right)\\ & = xyF_k(x,y) - xy\sum_{m=0}^{k-2}\sum_{n=0}^{\infty}\binom{n}m x^n y^m - x^ky^k\\ & = xyF_k(x,y) - xy\sum_{m=0}^{k-2}\frac{x^m}{(1-x)^{m+1}} y^m - x^ky^k\\ & = xyF_k(x,y) + 1 - \omega(x,y) - x^ky^k\\ \\ C & =\sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n-k-1,\,m-k,\,k) x^n y^m = x^{k+1}y^kF_k(x,y) \end{align} $$ Summing all the values we get: $$ F_k = \frac{1}{1-x} \cdot \omega + xF_k - \frac{x}{1-x} \cdot \omega + xyF_k + 1 - \omega - x^ky^k - x^{k+1}y^kF_k $$ And so (note that $\omega$ disappears): $$ F_k = \frac{1-x^ky^k}{1-x-xy-x^{k+1}y^k} $$
