Recurrence relations for strings of $0$'s and $1$'s of length $n$ where no $k$ consecutive $1$'s appear.

Question

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.

Answer 1

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$.

Answer 2

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)}$$