Solving recurrence of 3 variables using generating functions This comes from another question in Wilf's generatingfunctionology book (the part highlighted in light yellow):

If I read the question right, if I do it for $n=3$ (and assuming a substring like $111$ is considered to have 3 consecutive $1$'s and something like $01010$ has 2 non-consecutive $1$'s):
\begin{array}{|c|c|}
\hline
& m & k \\ \hline
000 & 0 & 0 \\ \hline
001 & 1 & 1 \\ \hline
010 & 1 & 1 \\ \hline
011 & 2 & 0 \\ \hline
100 & 1 & 1 \\ \hline
101 & 2 & 2 \\ \hline
110 & 2  & 0 \\ \hline
111 & 3 & 0 \\ \hline
\end{array}
So this means $f(3,1,1)=3, f(3,2,0)=2$ and $f(3,3,0) = 1$ for instance.
I have then found the recurrence in the form:
$$f(n,m,k) = f(n-1,m,k) + f(n-2,m-1,k-1) + \sum_{t \geq 0} {f((n-3)-t,(m-3)+1-t,k)}$$
Where:


*

*The first term is the case when we have $01$ at the start of the string.

*The 2nd term when we have $10$ at start of string.

*The 3rd term is when we have $110$, $1110$, $11110$, etc at the start of the string.


With base cases:


*

*$f(1,0,0)=f(1,1,1)=1$, and

*$f(n,n,0) =1$ if $n = 0$ or $n > 1$.


And also some other conditions, including $n,m,k\geq 0$, $n\geq m$ and $m\geq k$
This leads me to part (b) of the question where I could multiply the recursion by $x^n y^m$ and sum it, or sum for $n$ or $m$ separately by first defining $A_{m,k} = \sum _{n\geq 0} {f(n,m,k)x^n}$, for example. However, I am confused as to how to deal with the 3rd term.
I believe I may have read the question incorrectly (since there's a mentioning of $k=1,2,...$, but I'm having trouble understanding what the question is asking for otherwise), but am still curious if this recurrence could be solved and would like to ask for hints/help as to how to approach this recurrence, or if I am reading the question right.
Thank you!
 A: For the generating function we get  more or less by inspection that it
is given by
$$F_k(x, y) = (1+x+x^2+\cdots)
\\ \times \sum_{q\ge 0} (y+y^2+\cdots+y^{k-1})^q (x+x^2+\cdots)^q
\\ \times (1+y+y^2+\cdots+y^{k-1})
\\ = (1+x+x^2+\cdots)
\\ \times \sum_{q\ge 0} x^q y^q (1+y+\cdots+y^{k-2})^q (1+x+\cdots)^q
\\ \times (1+y+y^2+\cdots+y^{k-1})
.$$
This is
$$F_k(x, y) = \frac{1}{1-x} \frac{1}{1-xy(1-y^{k-1})/(1-y)/(1-x)}
\frac{1-y^{k}}{1-y}
\\ = \frac{1-y^{k}}{(1-x)(1-y)-xy(1-y^{k-1})}
\\ = \frac{1-y^k}{1-x-y+xy^k}.$$
For the explicit formula we write
$$F_k(x, y) = \frac{1-y^k}{1-y-x(1-y^k)}
= \frac{1-y^k}{1-y} \frac{1}{1-x(1-y^k)/(1-y)}.$$
Extracting the coefficient on $x^n$ first followed by $y^m$ we get
$$[x^n] [y^m] F_k(x,y) = 
[y^m] \frac{1-y^k}{1-y} \frac{(1-y^k)^n}{(1-y)^n}
= [y^m] \frac{(1-y^k)^{n+1}}{(1-y)^{n+1}}
\\ = [y^m] \frac{1}{(1-y)^{n+1}}
\sum_{q=0}^{n+1} {n+1\choose q} (-1)^q y^{kq}
\\ = \sum_{q=0}^{n+1} {n+1\choose q} (-1)^q
[y^{m-kq}] \frac{1}{(1-y)^{n+1}}
\\ = \sum_{q=0}^{\lfloor m/k \rfloor} {n+1\choose q} (-1)^q 
{m+n-kq\choose n}.$$
We now  present a combinatorial  recurrence. Observe that  $f(n,m,k) -
f(n,m,k-1)$ gives the  strings where a block of $k-1$  ones appears at
least once. Now there are two cases.  The first appearance is right at
the  beginning  or   at  the  end  and  we   get  $f(n-1,m+1-k,k)$  or
$f(n-1,m+1-k,k-1)$ possibilities because the run of $k-1$ ones must be
followed / preceded by a zero.   The second is that the inital segment
before the  first appearance of  such a block  has length $p\ge  0$ to
$n+m-k-1$ followed by the $k-1$ ones surrounded by zeros followed by a
string of  length $n+m-p-(k+1)$ from  the set  that has at  most $k-1$
consecutive  ones. This  yields with  $q$ the  number of  ones in  the
prefix
$$f(n,m,k) = f(n,m,k-1) + f(n-1,m+1-k, k) + f(n-1,m+1-k,k-1) \\ +
\sum_{p=0}^{n+m-k-1} 
\sum_{q=0}^m f(p-q, q, k-1) f(n-2+q-p, m+1-q-k,k).$$
There  is  some Maple  code  to  help  explore these  recurrences  and
generating functions  which also includes the  boundary conditions for
the recurrence.


with(combinat);

RL :=
proc(n, m, k)
    option remember;
    local res, iter;

    iter :=
    proc(restx, resty, d)
    local pos, cur, runlen;

        if restx = 0 and resty = 0 then
            cur := -1; pos := 1; runlen := 0;

            while pos <= m+n do
                if d[pos] <> cur then
                    cur := d[pos];
                    runlen := 1;
                else
                    runlen := runlen + 1;

                    if cur = 1 and runlen >= k then
                        break;
                    fi;
                fi;

                pos := pos + 1;
            od;

            if pos = n+m+1 then
                if cur = 0 or (cur = 1 and runlen < k)
                then
                    res := res + 1;
                fi;
            fi;
        fi;

        if restx > 0 then
            iter(restx-1, resty, [op(d), 0]);
        fi;
        if resty > 0 then
            iter(restx, resty-1, [op(d), 1]);
        fi;
    end;

    res := 0;
    iter(n, m, []);
    res;
end;

EX := (n, m, k) ->
coeftayl(coeftayl((1-y^k)/(1-x-y+x*y^k),
                  x=0, n), y=0, m);

EX2 := (n, m, k) ->
add(binomial(n+1,q)*(-1)^q*
    binomial(m+n-k*q, n), q=0..floor(m/k));

f :=
proc(n, m, k)
option remember;

    if n < 0 or m < 0 then return 0 fi;

    if n = 0 and m = 0 then return 1 fi;

    if n = 0 then
        if m <= k-1 then
            return 1
        else
            return 0
        fi;
    fi;

    if m = 0 then return 1 fi;

    if k <= 1 then return 0 fi;

    f(n,m,k-1) + f(n-1,m+1-k,k) + f(n-1, m+1-k, k-1) +
    add(add(f(p-q, q, k-1)*f(n-2+q-p, m+1-q-k, k),
            q=0..m), p=0..n+m-k-1);
end;

There   is  also   a  recurrence   that  is   algebraic  rather   than
combinatorial. We start from the observation that
$$\frac{\partial}{\partial x} F_k(x, y) = F_k^2(x, y).$$
Extracting coefficients on $[x^{n-1}] [y^m]$ yields
$$f(n, m, k) = \frac{1}{n} \sum_{p=0}^{n-1} \sum_{q=0}^m
f(p, q, k) f(n-1-p, m-q, k).$$
This is implemented below.

g :=
proc(n, m, k)
option remember;

    if n < 0 or m < 0 then return 0 fi;

    if n = 0 and m = 0 then return 1 fi;

    if n = 0 then
        if m <= k-1 then
            return 1
        else
            return 0
        fi;
    fi;

    if m = 0 then return 1 fi;

    if k <= 1 then return 0 fi;

    1/n*add(add(g(p, q, k)*g(n-1-p, m-q, k),
                q=0..m), p=0..n-1);
end;

