How can we solve a multi-variable recurrence relation in closed form, when the number of terms is also variable? Consider the formula
$f(x, y) = f(x, y-1) + 2 \sum\limits_{i=1}^{x-1} f(i, y-1) $
The factor '2' makes this not expressible cleanly as $f(x, y) = f(x, y-1) + f(x-1, y)$, which is solved here using generating functions.
In this case, the edge conditions are
$f(x, 1) = 2x - 1$
$f(1, y) = 1$
How can this sort of formula be expressed in closed form?
 A: Argh... better write this as:
$$
f(k + 1, n + 1) = f(k + 1, n) + 2 \sum_{1 \le i \le n} f(i, n)
$$
Define $F(x, y) = \sum_{k, n \ge 1} f(k, n) x^k y^n$, multiply the recurrence by $x^k y^n$, sum over $k \ge 1$ and $n \ge 1$. Recognize the resulting sums
$$
\frac{F(x, y) - \sum_{k \ge 1} f(k, 1) x^k - \sum_{n \ge 1} f(1, n) y^n + f(1, 1)}{x y}
  = \frac{F(x, y) - \sum_{n \ge 1} f(1, n) y^n}{x}
      + 2 \frac{F(x, y)}{1 - y}
$$
You also have the boundary conditions:
$\begin{align}
\sum_{k \ge 1} f(k, 1) x^k
  &= \sum_{k \ge 1} (2 k - 1) x^k \\
  &= \frac{2 x}{(1 - x)^2} - \frac{1}{1 - x} \\
  &= \frac{3 x - 1}{(1 - x)^2} \\
\sum_{n \ge 1} f(1, n) y^n
  &= \frac{1}{1 - y} \\
f(1, 1)
  &= 1
\end{align}$
Plugging all this in and solving for $F(x, y)$:
$$
F(x, y)
  = \frac{(1 - 3 x)(1 - y)}
         {(1 - x)^2 ((1 - y)^2 - 2 x y)}
$$
Next step would be to split into partial fractions by $x$, and the results by $y$, to read off the coefficients. It looks doable, but messy. I'll leave it here.
