How to solve this recurrence Solve the recurrence
\[
f_{j,k}^{(l)} =
\begin{cases}
\left[j>k\right] j^{k-1}(j-k), &\qquad j=l \\
\\
\left[j>k+1\right] \sum_t \binom k t f_{j-1,k-t}^{(l)}, &\qquad j>l
\end{cases}
\]
for all nonnegative integer $k$ and postive integers $j$, $l$, where
\[
[P] = \begin{cases}
1, &\qquad \hbox{if $P$ is true} \\
0, &\qquad \hbox{otherwise}
\end{cases}
\]
is Iverson bracket, see Wikipedia. For example, $[2 < 3] = 1; [2 > 3] = 0$
The problem is introduced from a programming problem from URAL. I'm trying to find a closed form solution for the problem (notice that $f_{j,k}^{(l)}$ is the number of arrangements of $j$ horses and $k$ students in which the last horse is empty and the adjacent $l$ horses are not all occupied).
Here I want to show an algebraic way, to obtain $f_{j,k}^{(l)} = [j>k] j^{k-1}(j-k), \qquad j=l$ which I got through combinatorial interpretation, that I think helpful to solve the recurrence of $f_{j,k}^{(l)}$. In fact, $[j>k] j^{k-1}(j-k)$ is the solution to the following recurrence:
\begin{align*}
g_{1,k} &= \left[k \le 1\right] (1 - k), \qquad k \ge 0 \\
g_{j,k} &= \left[k < j\right] \sum_t \binom k t g_{j-1,k-t}, \qquad j > 1, k \ge 0
\end{align*}
Notice that the recurrence of $g$ is similiar with that of $f^{(l)}$. It seems to be as strange as the recurrence of $f^{(l)}$, but it isn't too messy.
Let's solve it by hand. First assume that
\begin{align*}
g_{1,k}^* &= 1 - k, \qquad k \ge 0 \\
g_{j,k}^* &= \sum_t \binom k t g_{j-1,k-t}, \qquad j > 1, k \ge 0
\end{align*}
We have $g_{1,k}^* = g_{1,k}$ for $0 \le k \le 1$. Now let's consider the exponential generating function for $g_{j,k}^*$: $\hat G_j^*(z) = \sum_{k \ge 0} g_{j,k}^* z^k/k!$.
\begin{align*}
\hat G_1^*(z)
&= \sum_{k \ge 0} \frac{(1-k)z^k}{k!} \\
&= \sum_{k \ge 0} \left(\frac{z^k}{k!} - \frac{kz^k}{k!}\right) \\
&= \sum_{k \ge 0} \frac{z^k}{k!} - \sum_{k \ge 0} \frac{z^{k+1}}{k!} \\
&= (1-z)e^z
\end{align*}
and for $j > 1$,
\begin{align*}
\hat G_j^*(z)
&= \sum_{k \ge 0} \sum_{0 \le t \le k} \frac{g_{j-1,k-t}^*z^k}{t!(k-t)!} \\
&= \sum_{t \ge 0} \frac{z^t}{t!} \sum_{k \ge t} \frac{g_{j-1,k-t}^*z^{k-t}}{(k-t)!} \\
&= \sum_{t \ge 0} \frac{z^t}{t!} \sum_{k \ge 0} \frac{g_{j-1,k}^*z^k}{k!} \\
&= e^z \hat G_{j-1}^*(z)
\end{align*}
so $\hat G_j^*(z) = (1-z)e^{jz}$, and we get $g_{j,k}^* = j^{k-1}(j-k)$, and $g_{k,k}^* = g_{k,k} = 0$ whenever $k \ge 1$.
Now it's easy to prove $g_{j,k} = g_{j,k}^*$ for $0 \le k \le j$ by induction on $j$.
Can we solve $f_{j,k}^{(l)}$ like this? More precisely, extend some zeros of $f_{j,k}^{(l)}$ to nonzeros to eliminate the awful factor $[j > k + 1]$ in recurrence, solve it and prove that the nonzeros of $f_{j,k}^{(l)}$ keeps its value when extending?
Thanks for your help!
 A: The usual presentation for this problem is determining the expected running time in terms of the load and the size of the table of inserting into a hash table with linear probing. Knuth himself was interested in this problem (Notes on "Open" Addressing, 1963).
A: Let the known solution at $$j=l$$ define the generating function $$g^l(z)\equiv \sum_{k\ge 0} j^{k-1}(j-k)z^k = \frac{1-(j+1)z}{(1-jz)^2}.$$ For larger $j$ the sequence of $k$ is given by repeated/recursive application of a binomial transform, where the associated effect on the generating function is $$g^{j}(z) = \frac{1}{1-z}g^{j-1}(\frac{z}{1-z})$$. See for example equation (58) in http://www.mpia.de/~mathar/public/mathar20071126.pdf This effectively leads to the generating function $$g^{l+i}(z) = \frac{1-(i+1+j)z}{[1-(i+j)z]^2},\, i\ge 0.$$ The partial fraction decomposition of this is $$g^{l+i}(z) = \frac{j+i+1}{j+i}\frac{1}{1-(i+j)z}-\frac{1}{j+i}\frac{1}{[1-(j+i)z]^2}.$$ The result has the same format at the one obtained for $j=l$ just substituting $j\to i+j$. So from that it appears $f_{j+i,k}^{(l)} = (i+j)^{k-1}(i+j-k)$. This is just a rough analysis which does not yet take into account that the generating function should be truncated at $k=j$ instead extending to infinity.
