Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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$ –  Thomas Andrews Nov 9 '11 at 17:48
2  
@JoelCohen: Isn't the answer ${i+j}\choose i$? –  Thomas Andrews Nov 9 '11 at 18:03
    
@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. –  Joel Cohen Nov 9 '11 at 18:12
    
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}$. –  Byron Schmuland Nov 9 '11 at 18:20
    
(My note above is wrong. (x+y)f(x) = f(x) - some functions –  Thomas Andrews Nov 9 '11 at 18:23

1 Answer 1

up vote 5 down vote accepted

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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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