How to solve this multivariate recurrence with Mathematica?

Question

I would like to solve this recurrence relation:
$a_{m,n}=a_{m-1,n}+a_{m,n-1}$ with $a_{0,0}=0, a_{m,0}=1, a_{0,n}=1$
Related to the Tartaglia triangle,

the solution should be just the combinations...
$a{m,n}=Binomial(m+n,n)$

But when I try to solve it with Mathematica

RSolve[{a[m, n] == a[-1 + m, n] + a[m, -1 + n], a[0, 0] == 0, 
  a[m, 0] == 1, a[0, n] == 1}, a[m, n], {m, n}]  

It just outputs the same input unevaluated.

What am I doing wrong?

Answer 1

maybe you know this, but you don't need RSolve if you just want to crunch out the numbers.

Clear[a];
a[0, 0] = 0; a[m_, 0] = 1; a[0, n_] = 1;
a[m_, n_] := a[-1 + m, n] + a[m, -1 + n]
Column[Table[
  Row[Framed[#, FrameMargins -> 10] & /@ 
    Table[a[i, k - i], {i, 0, k}], " "], {k, 0, 8}], Center]

this seems to validate your formulation, except it seems a[0,0] should be 1 (that doesn't make RSolve any happier though )

I suspect RSolve simply cant handle it, but you might try mathematica.stackexchange.com.

aside, if you need to use this for large numbers you probably should use memoization:

 a[m_, n_] := a[m,n] = a[-1 + m, n] + a[m, -1 + n]

for completeness the expected answer is a[i,j]=Binomial[i+j,j]