1
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.