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

Tag: recursion , wolfram-mathematica Author: relaxwhynot Date: 2010-09-18

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"

Other Answer1

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

comments:

OK, but where you say P[N,0], isn't that equal to 1 by my conditions above? I'm pretty sure this recursion works, since I can calculate it in Mathematica, albeit not in closed form.
In your original task, are m & n one-based? If they are one-based, then there's no rule to calculate P[3,2], because both the first and the third rule try to refer to P[3,0]. If they are zero-based, then the value of P[3,0] is undefined.
Also, what happens if you try to compute p[3,1] ??? ...should it try to follow the path p[3,m] or p[n,1] ? ...both leading to different solutions. One value, several pathes ...problematic. Your problem is ill-defined in many ways.
@user354134 Could you explain how did you arrive at these eqs. from the Risk Odds Calculator? Perhaps something is loose there ...

Other Answer2

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.

comments:

Not sure this helps at all, but: "p[n-1,m+1]-p[n,m] == p[n,m-2] - p[n-3,m]" holds, and makes me wonder if m-n is the key here somehow.
Those still aren't in a straight line like all the other examples. Why do you need it anyway? Just a personal challenege? If you actually need to compute it, you could just memoize 100x100 results.