How to solve this multivariate recurrence with Mathematica?

1
votes

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$
Its outputs form 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?

1
wolfram-mathematicarecurrence
The initial condition a[m,0]=1 contradicts the initial condition a[0, 0]=0 when m=0. - Angela Pretorius
perhaps the initial conditions should be at a[1,0] and a[0,1] - agentp
@AngelaRichardson I want a[m,0]=1 for all m except 0. Anyway I've also tried with different conditions and without any. - skan
@agentp it doesn't work either - skan
Curiously the Euler recurrence equation here is also unsolved. - Chris Degnen

1 Answers

2
votes

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]

enter image description here

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]