A formula for bit strings with no $k$ consecutive $1$'s using generating functions 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}
$$
 A: First of all, some unsolicited advice: your derivation for (b) need not be so messy.  It greatly simplifies things to observe that
$$
f(n,m,k) = f(n-1,m,k) + f(n-1,m-1,k) - f(n-k-1,m-k,k) \tag{1}
$$
holds not just when $0 \le k \le m \le n$, $k < n$.  In fact, it holds for any $n \ge 0, m \ge 0, k \ge 1$, except in the two cases $m = n = k$, and $m = n = 0$.  This of courses assumes that $f(n,m,k) = 0$ if $n < 0$ or $m < 0$.
Proof:


*

*If $m > n$, then the LHS and RHS of (1) are both zero, so the equation holds.

*If $m \le n$ and $k > m$, then the LHS is ${n \choose m}$, while the RHS is
${n-1 \choose m} + {n-1 \choose m-1} + 0$, so (1) holds, unless $n = 0$ in which case we have the first exception $m = n = 0$.

*If $m \le n$ and $k \le m$ and $k < n$, then (1) holds by the counting argument you gave.

*If $m \le n$ and $k \le m$ and $k \ge n$, i.e. $k = m = n$, then the LHS is $0$ while the RHS is $0 + 1 - 0 = 1$, so we have the second exception.
This covers all cases.  So then you can just write
\begin{align*}
F_k(x,y) & = \sum_{n,m\ge0}f(n,m,k) x^n y^m \\
& = 1 - x^k y^k \\
&\quad + \sum_{n,m\ge0}
\big[ f(n-1,m,k) + f(n-1,m-1,k) - f(n-k-1, m-k,k) \big] x^n y^m \\
&= 1 - x^k y^k + (x + xy - x^{k+1} y^k) F_k(x,y) \\
F_k(x,y) &=
\frac{1 - x^k y^k}{1 - x - xy + x^{k+1}{y^k}}.
\end{align*}
Then you avoid all the gross introduction of $\omega$, etc. ;)
For part (c)
Write as follows:
\begin{align*}
F_k(x,y)
&= \frac{1 - x^k y^k}{1 - x - xy + x^{k+1}{y^k}} \\
&= \frac{1 - x^k y^k}{1 - xy - x(1 - x^ky^k)} \\
&= \frac{1}{x} \left( \frac{x(1 - x^k y^k)}{1 - xy - x(1 - x^ky^k)} \right) \\
&= \frac{1}{x} \left( \frac{1 - xy - \left[1 - xy - x(1 - x^k y^k)\right]}{1 - xy - x(1 - x^ky^k)} \right) \\
&= \frac{1}{x} \left( \frac{1 - xy}{1 - xy - x(1 - x^ky^k)} - 1 \right) \\
&= \frac{1}{x} \left( \frac{1}{1 - x(1 + xy + x^2y^2 + \cdots + x^{k-1}y^{k-1})} - 1 \right) \\
\end{align*}
Now,
\begin{align*}
&\; \frac{1}{1 - x(1 + xy + x^2y^2 + \cdots + x^{k-1}y^{k-1})} \\
&= \sum_{N \ge 0} x^N \left(1 + xy + x^2y^2 + \cdots + x^{k-1}y^{k-1}\right)^N \\
\end{align*}
We want the coefficient of $x^{n+1}y^m$ in this series (because then this will multiply by $\frac{1}{x}$ to give us the coefficient of $x^n y^m$, $f(n,m,k)$.)
For the coefficient of $x^{n+1} y^m$, we need $N = n + 1 -m$.  So we want the coefficient of $x^m y^m$ in
$$
\left(1 + xy + x^2y^2 + \cdots + x^{k-1}y^{k-1}\right)^{n+1-m}
=
\frac{(1 - x^k y^k)^{n+1-m}}{(1 - xy)^{n+1-m}}
$$
Now write out the series for $\frac{1}{(1 - xy)^{n+1-m}}$ explicitly, and expand $(1 - x^k y^k)^{n+1-m}$ with the binomial formula, and you should be able to find a finite summation yielding the coefficient of $x^{n+1} y^m$, which will equal $f(m,n,k)$.
A: As long as you're working on these types of problems in Wilf's book, you might also want to read a truly wonderful article by Noonan and Zeilberger on the Goulden-Jackson cluster method. It generalizes the above problem to avoid any collection of words (not just $k$ 1's in a row), and the method is no more complex than your calculation.
