Solve recurrence of form p[n,m]==p[n,m-2]+p[n-1,m-1]+p[n-2,m]

Question

I'm trying to solve (find a closed-form solution to) this (Risk odds calculator) recurrence relation:

p[n,m] == 2890/7776*p[n,m-2] + 2611/7776*p[n-1,m-1] + 2275/7776*p[n-2,m],
p[n,1] == 855/1296 + 441/1296*p[n-1,1],
p[3,m] == 295/1296*p[3,m-2] + 420/1296*p[2,m-1],
p[2,m] == 55/216,
p[1,m] == 0

Mathematica's RSolve function doesn't work (I'm sure I'm using the right syntax, since I'm following the two-variable examples at http://reference.wolfram.com/mathematica/ref/RSolve.html).

In fact, RSolve won't even solve this "simpler" recursion:

p[n,m] == p[n,m-2] + p[n-1,m-1] + p[n-2,m],
p[0,m] == 1,
p[1,m] == 1,
p[n,1] == 1,
p[n,0] == 1

Is there something fundamentally hard about solving this type of recurrence relation or is Mathematica just being flaky?

The exact example I'm using:

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

The return value is the same as my input, up to some number juggling.

On the doc page, it's under "Scope" and then "Partial Difference Equations"

Answer 1

Disclaimer: I know just a little linear algebra and some calculus. I don't know anything about Wolfram.

It might be that there's something fundamentally hard about it. The examples that you linked to are all easier than yours. For instance, look at this example:

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

All the a[m,n] are on a straight line, m+n=k for some constant k. Like say you know a[10,5]. From that you can compute a[11,4], a[12,3], etc. But they're all on a straight line. That's why the output includes some function of m+n. You could re-write it with just one variable and get the same effect:

RSolve[{a[m + 1] - 3/4 a[m] == 0, m+n=k}, a[m], {m, n}]

All the examples in that link are on a straight line, too. For every a[m,n] that you need to know, n is always a function of m. Anything of that form is easy to solve with linear algebra matrices. (Let me know if you want to know about how to do those.)

For yours, however, that isn't the case. Yours expands like a tree, not like a line. I think that that might be the difficulty.

It kind of reminds me of the difference between partial derivatives and total derivatives. That might be a good starting point.

Answer 2

...just my two cents, but isn't this system of equations flawed? I.e.:

p[n,m] == 2890/7776*p[n,m-2] + 2611/7776*p[n-1,m-1] + 2275/7776*p[n-2,m]

For instance, let's try to compute p[N,2]:

p[N,2] = 2890/7776*p[N,0] + ...
       = 2890/7776*2890/7776*p[N,-2] + ...
       = ... p[N,-4] + ...

I guess you got my point. It will never reach an initial condition for an even m. Same for:

p[3,m] == 295/1296*p[3,m-2] + ...

On the opposite, the initial condition p[1,m] == 0 will never be used. Perhaps adding a definition for p[n,0] or p[n,2] would solve your problem by making it well defined.