Recurrence relations for strings of $0$'s and $1$'s of length $n$ where no $k$ consecutive $1$'s appear. This question is related to this one, but the answers there do not explain my confusion.
This is exercise 20 in page 28 in the book generatingfunctionology:
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. Then
(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\geq 0}f(n,m,k)x^ny^m\quad(k=1,2,...)$$
Here's what I have:
I didn't get exactly three terms in the recurrence, but I did come up with one plausible. Well, we want to use $n-m$ $0$'s to separate $m$ $1$'s. That's the same as putting $m$ balls into $n-m+1$ ordered boxes, and each box can at most contain $k-1$ balls. We divide the cases by how many balls the last box has: it could be $0,1,...,k-1$. Hence we have the recurrence relation:
$$f(n,m,k)=\sum_{i=1}^{k}f(n-i,m-i+1,k)$$
This recurrence should hold for arbitrary $n,m,k$ as long as we specify the appropriate initial values, or at least it should hold for $k$ large enough. (This might be where I ran into problems but I can not see it immediately).
However, when I carry this to the next part I am confused, because
\begin{aligned}
 F_k(x,y)& = \sum_{n,m\geq 0}f(n,m,k)x^ny^m \\
& = \sum_{n,m\geq 0}\sum_{i=1}^{k}f(n-i,m-i+1,k)x^ny^m \\
& = \sum_{i=1}^k\sum_{n,m\geq 0}f(n-i,m-i+1,k)x^ny^m \\
& = \sum_{i=1}^kx^iy^{i-1}\sum_{n,m\geq 0}f(n-i,m-i+1,k)x^{n-i}y^{m-i+1}\\
& = \sum_{i=1}^kx^iy^{i-1}F_k(x,y)
\end{aligned}
The second to bottom equality holds in my mind because $f(m,n,k)=0$ if either of $m$ or $n$ is $0$. However, it confuses me since at the end the equation implies $F_k(x,y)=0$?
Where did I go wrong? Any kind of help would be appreciated.
 A: Your recurrence relation needs a base case: as written, it does not hold when $n=0$.
$$
f(0,0,k) = 1\\\qquad\;\;\;\;\;\;\;\;\;\;
f(0,m,k) = 0\qquad (m>0)
$$
Incorporating this into your generating function calculations should allow you to solve for $F$.
A: Based on @Mike Earnest's help, I revised my solution and include it here in case it helps anyone. It also coincides with @robjohn's answer in this post, which I didn't get at the beginning.
\begin{aligned}
f(n,m,k) = \begin{cases}
\sum_{i=1}^k f(n-i,m-i+1,k),\quad n>m \\
0\;\quad\qquad\qquad\qquad\qquad ,\quad n<m \\
[n<k]\qquad\qquad\qquad\quad,\quad n=m
\end{cases} 
\end{aligned}
Hence,
\begin{aligned}
F_k(x,y) & =\sum_{n,m\geq 0}f(n,m,k)x^ny^m \\
 & = \sum_{ n > m\geq 0}f(n,m,k)x^ny^m + \sum_{ n = m\geq 0}[n<k]x^ny^m\\
& = \sum_{n>m}\sum_{i=0}^kf(n-i,m-i+1,k)x^ny^m+\sum_{ n = 0}^{k-1}x^ny^n \\
& = \sum_{i=1}^kx^iy^{i-1}\sum_{n>m\geq 0}f(n-i,m-i+1,k)x^{n-i}y^{m-i+1}+\sum_{ n = 0}^{k-1}x^ny^n \\
& = \sum_{i=1}^kx^iy^{i-1}F_k(x,y) + \frac{x^ky^k-1}{xy-1} \\
& = \frac{x(x^ky^k-1)}{xy-1}F_k(x,y) + \frac{x^ky^k-1}{xy-1}
\end{aligned}
where
$$[n<k]=\begin{cases}1\quad, n<k \\ 0\quad, n\geq k \end{cases}$$
Finally we get
$$F_k(x,y)=\frac{x^ky^k-1}{xy-1-x(x^ky^k-1)}$$
