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

  • 4
    That's certainly a good way to start. All such problems, however, need initial conditions, such as, say, $c(0,j)=c(i,0)=1$. A common approach is to use a generating function $f(x,y)=\sum_{i,j} c_{ij}x^iy^j$. Then $(x+y)f(x) = f(x) + \sum_{i} c_{i0} x^i + \sum_{j}c_{0j} y^j$2011-11-09
  • 2
    @JoelCohen: Isn't the answer ${i+j}\choose i$?2011-11-09
  • 0
    @ThomasAndrews : You're right. My bad :) I initially wanted to write that $2^{i+j}$ was "a solution" (because there was no initial condition at the time) and then changed it to "the solution" without actually checking it.2011-11-09
  • 0
    As an aside, this recursion shows up in the ballot problem. The region is the wedge $i\geq j\geq 0$ and the boundary conditions are $c_{i,i}=0$ for $i\geq 0$ and $c_{i,0}=1$ for $i\geq 1$. The solution is $c_{i,j}={i-j\over i+j}{i+j\choose j}$.2011-11-09
  • 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}$.