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

• Is that really supposed to be an $n$ in the upper limit on the summation, or should it be an $x$? – Nick Peterson Jul 10 '15 at 19:27

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.