# 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?

-
Unimportant note: what you write $[j>k]$ is also written (more usually?) as $u(j-k-1)$, where $u(\cdot)$ is the unit step (or Heaviside) function – leonbloy Jun 1 '12 at 13:42
Which is "more usual" depends on what branch of mathematics you are doing. – GEdgar Jun 1 '12 at 13:59
@leonbloy I knew the notation from Concrete Mathematics and The Art of Computer Programming and here's another reference: en.wikipedia.org/wiki/Iverson_bracket – Frank Science Jun 1 '12 at 14:07
Yes, I'm not objecting to it, just pointing the alternative in case someone find it easier to deal with. BTW "houses" or "horses" ? (and "students"?). BTW2: Are you interested in solving this recursion or just in solving analitically the original problem? – leonbloy Jun 1 '12 at 14:09
@GEdgar More details? I can't get your idea. – Frank Science Jun 1 '12 at 14:11