3
$\begingroup$

How do i solve a recursion like this:

$c_{i,j} = c_{i,j-1} + c_{i-1,j}$ with $c_{i,0} = c_{0,j} = 1$

After one step it can be written as:

$c_{i,j} = c_{i,j-2} + 2c_{i-1,j-1} + c_{i-2,j-1}$

which reminds me of $(x+y)^2$

But all my approaches failed to get a close form.

Thank you

  • 0
    (My note above is wrong. (x+y)f(x) = f(x) - some functions2011-11-09

1 Answers 1

6

It depends on the range of values for $i$ and $j$, and some initial values for $c_{ij}$.

The common way to solve a linear recurrence of this sort is to use generating functions.

Assume your initial conditions are on $c_{i0}$ and $c_{0j}$, and $i,j$ are supposed to be non-negative integers. Define:

$f(x,y) = \sum_{i,j} c_{ij} x^i y^j$

Then:

$(x+y) f(x,y) = f(x,y) - c_{00} - \sum_{i>0}(c_{i0}-c_{i-1,0})x^i - \sum_{j>0} (c_{0j}-c_{0,j-1}) y^j$

For the particular $c_{0j}=c_{i0}=1$, this resolves to the nice formula:

$f(x,y) = \frac{1}{1-(x+y)}$

But $\frac{1}{1-(x+y)} = \sum_m (x+y)^m = \sum_{i,j} {{i+j}\choose i} x^iy^j$

So $c_{ij} = {{i+j}\choose i}$.