Can 2-Index Recurrence Relations with Constant Coefficients Be Solved Generally?

[Adeimantus]

Is there a general method for solving 2-index recurrence relations with constant coefficients? Here is one I would like to solve


a_{m,n} = \frac{xa_{m-1,n} + ya_{m,n-1} + 1}{x+y} for m,n > 0

with initial conditions

a_{m,0} = m/x and a_{0,n} = n/y.


Hoping for an analogy with PDE's, I tried separation of variables for the homogeneous part of the solution: a^h_{m,n} = M_mN_n. But I couldn't figure out how to match the initial conditions. I don't think that is the right approach.

thanks :)

 

[bpet]

Is there a general method for solving 2-index recurrence relations with constant coefficients? Here is one I would like to solve


a_{m,n} = \frac{xa_{m-1,n} + ya_{m,n-1} + 1}{x+y} for m,n > 0

with initial conditions

a_{m,0} = m/x and a_{0,n} = n/y.


Hoping for an analogy with PDE's, I tried separation of variables for the homogeneous part of the solution: a^h_{m,n} = M_mN_n. But I couldn't figure out how to match the initial conditions. I don't think that is the right approach.

thanks :)

Sounds like you're on the right track. What expression did you get for the inhomogeneous part of the solution?

 

[Adeimantus]

Sounds like you're on the right track. What expression did you get for the inhomogeneous part of the solution?

I tried a particular solution of the form Am+Bn+C. That results in


(x+y)(Am+Bn+C) - x(A(m-1)+Bn+C)-y(Am+B(n-1)+C) = 1

or Ax+By = 1 and C is undetermined. So I was thinking A = 1/2x, B = 1/2y. But the homogeneous solutions for M_m and N_n are exponential, so I don't know how this form of solution will satisfy the initial conditions a_{m,0} = m/x, a_{0,n} = n/y.

 

[bpet]

I tried a particular solution of the form Am+Bn+C. That results in


(x+y)(Am+Bn+C) - x(A(m-1)+Bn+C)-y(Am+B(n-1)+C) = 1

or Ax+By = 1 and C is undetermined. So I was thinking A = 1/2x, B = 1/2y. But the homogeneous solutions for M_m and N_n are exponential, so I don't know how this form of solution will satisfy the initial conditions a_{m,0} = m/x, a_{0,n} = n/y.

Sounds right so far. What does the general solution look like before matching the boundary conditions?

 

[Adeimantus]

Substituting in M_mN_n for the homogeneous solution gives

x+y -x\frac{M_{m-1}}{M_m} -y\frac{N_{n-1}}{N_n} = 0

So if xM_m-1/M_m = -k, where k is some constant, then M_m = M_1\left(\frac{-x}{k}\right)^{m-1} and N_n = N_1\left(\frac{y}{x+y+k}\right)^{n-1}

Putting it all together gives

a_{m,n} = M_1N_1\left(\frac{-x}{k}\right)^{m-1}\left(\frac{y}{x+y+k}\right)^{n-1} + \frac{m}{2x} + \frac{n}{2y} + C

But I don't see any way of choosing the constants to match the IC's.


Edit: BTW, the motivation for this problem is finding the expected number of rolls it takes to get m 7's and n 11's with a pair of dice. In this case, x = 6/36 = 1/6 is the probability of rolling a 7 and y = 2/36 = 1/18 is the probability of rolling an 11. You find the expected number of rolls recursively by conditioning on the outcome of the first roll.

 

[bpet]

Putting it all together gives

a_{m,n} = M_1N_1\left(\frac{-x}{k}\right)^{m-1}\left(\frac{y}{x+y+k}\right)^{n-1} + \frac{m}{2x} + \frac{n}{2y} + C

Should that be

a_{m,n} = \sum_k C_k\left(\frac{-x}{k}\right)^m\left(\frac{y}{x+y+k}\right)^n + \frac{m}{2x} + \frac{n}{2y}

 

[Adeimantus]

Should that be

a_{m,n} = \sum_k C_k\left(\frac{-x}{k}\right)^m\left(\frac{y}{x+y+k}\right)^n + \frac{m}{2x} + \frac{n}{2y}

Indeed, it should be. thanks for pointing that out. I'm still not sure how to proceed, but at least that gives me something to work with.

 

[bpet]

Indeed, it should be. thanks for pointing that out. I'm still not sure how to proceed, but at least that gives me something to work with.

Come to think of it, I'm not sure either :)

The problem is, even after boundedness constraints k can be any value from a continuous interval, so the sum is probably an integral. There might be a way of solving the coefficients using orthogonality but I'm not sure.

Maybe the recurrence can be solved from scratch using the Z-transform?

 

[Adeimantus]

In the meantime, I found another method of doing it by searching online. The idea is to use a generating function

F(w,z) = \sum_{m=1}^\infty\sum_{n=1}^\infty a_{m,n}w^mz^n

I did this for the special case x = y = 1/2 in the original recurrence. In other words,

a_{m,n} = (1/2)(a_{m-1,n} + a_{m,n-1}) + 1
a_{m,0} = 2m
a_{0,n} = 2n

The idea is to use the recurrence relation to solve for F(w,z). I got

F(w,z) = \frac{2wz}{(2-w-z)(1-w)^2} + \frac{2wz}{(2-w-z)(1-z)^2} + \frac{2wz}{(1-w)(1-z)(2-w-z)}

Then, finding the coefficient of w^mz^n in the power series expansion of F(w,z) gives the awful expression

a_{m,n}=\sum_{j=0}^n\frac{n-j}{2^{m+j-1}}\left( ^{m+j-1}_j\right)<br /> + \sum_{j=0}^m\frac{m-j}{2^{n+j-1}}\left( ^{n+j-1}_j\right)<br /> + \sum_{j=1}^n\sum_{k=0}^{m-1}\frac{1}{2^{k+j-1}}\left( ^{k+j-1}_j\right)<br />


The values obtained from this formula seem to match the ones obtained directly from the recurrence relation, so I guess it is right. But even this formula does not seem to match the initial
conditions. If you put in m=0, for instance, it looks like the formula gives a_0,n = 0. So that makes me wonder if the general formula for a_m,n has to hold for the I.C.'s also? I would still like to figure out how to solve this with the separation of variables method.

edit:

Maybe the recurrence can be solved from scratch using the Z-transform?

while looking around online, I saw someone refer to z-transforms for solving recurrences. So maybe I should look up that method on Wikipedia.

 

[bpet]

But even this formula does not seem to match the initial conditions. If you put in m=0, for instance, it looks like the formula gives a_0,n = 0.

The argument looks right - Z-transform is the same idea. The generating function won't give a_{0,n} because m=0 wasn't included in its definition. You could include m=0 and n=0 if you like, and would get the same results for m>0 and n>0 in the end.

Could you please check the formula for a_{m,n} because it gives indeterminate values for m=1 and n=1.

 

[Adeimantus]

The argument looks right - Z-transform is the same idea. The generating function won't give a_{0,n} because m=0 wasn't included in its definition. You could include m=0 and n=0 if you like, and would get the same results for m>0 and n>0 in the end.

OK, that makes sense.

Could you please check the formula for a_{m,n} because it gives indeterminate values for m=1 and n=1.

Are you referring to the presence of choose(j-1, j) in the last term? I guess I really should start the sum at k=1 since the k=0 term is zero. I haven't double-checked my derivation of that formula, but I did write a short program to see if it matches with the recursively calculated a_m,n, and it seems to for everything except m = 0 or n = 0.

The Z-transform pair approach looks cool. It seems like you could transform one index at a time, but I haven't tried it yet.

 

[Adeimantus]

Applying the Z-transform (which, as you said, is pretty much the same thing as
using a generating function) to the second index results in the following
answer for the general case:

a_{m,n} = \frac{m}{x} + \frac{1}{y} \left( \frac{x}{x+y} \right)^m<br /> \sum_{j=0}^{n-1} \left( \frac{y}{x+y} \right)^j \left( _{j}^{j+m-1} \right)<br />

No double sum! Thank you for the suggestion. :) I modified the C program I
wrote before to calculate this, and it seems to agree with the recursively
calculated a_m,n

 

[bpet]

Applying the Z-transform (which, as you said, is pretty much the same thing as
using a generating function) to the second index results in the following
answer for the general case:

a_{m,n} = \frac{m}{x} + \frac{1}{y} \left( \frac{x}{x+y} \right)^m<br /> \sum_{j=0}^{n-1} \left( \frac{y}{x+y} \right)^j \left( _{j}^{j+m-1} \right)<br />

No double sum! Thank you for the suggestion. :) I modified the C program I
wrote before to calculate this, and it seems to agree with the recursively
calculated a_m,n

Nice :) Are you sure though? For a(2,2) I get 5.5 using the recursion and 5 using the above formula at x=y=1/2. Also I wonder if there is a solution that is symmetric interchanging (m,x) with (n,y).

 

[Adeimantus]

Nice :) Are you sure though? For a(2,2) I get 5.5 using the recursion and 5 using the above formula at x=y=1/2.

Ah, good catch! I left out a factor of n-j in the sum when I posted it here, but I had it right in my program. So it should be


a_{m,n} = \frac{m}{x} + \frac{1}{y} \left( \frac{x}{x+y} \right)^m\sum_{j=0}^{n-1} (n-j)\left( \frac{y}{x+y} \right)^j \left( _{j}^{j+m-1} \right)

Also I wonder if there is a solution that is symmetric interchanging (m,x) with (n,y).

I was wondering the same thing. The best thing I can come up with is to make the (m,x) <=> (n,y) switch in the above formula, add the two formulas, and then divide by 2. That would be symmetric, but not particularly enlightening. However, it does start to resemble the form we were encountering when trying the separation of variables method... I'll have to take a look at that.