2-index recurrence relations

1. Feb 28, 2009

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 :)

2. Mar 1, 2009

bpet

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

3. Mar 1, 2009

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

4. Mar 1, 2009

bpet

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

5. Mar 1, 2009

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.

Last edited: Mar 1, 2009
6. Mar 1, 2009

bpet

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}$$

7. Mar 1, 2009

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.

8. Mar 1, 2009

bpet

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?

9. Mar 1, 2009

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) + \sum_{j=0}^m\frac{m-j}{2^{n+j-1}}\left( ^{n+j-1}_j\right) + \sum_{j=1}^n\sum_{k=0}^{m-1}\frac{1}{2^{k+j-1}}\left( ^{k+j-1}_j\right)$$

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:
while looking around online, I saw someone refer to z-transforms for solving recurrences. So maybe I should look up that method on Wikipedia.

Last edited: Mar 1, 2009
10. Mar 1, 2009

bpet

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.

11. Mar 2, 2009

OK, that makes sense.

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.

Last edited: Mar 2, 2009
12. Mar 2, 2009

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

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

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

13. Mar 2, 2009

bpet

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

14. Mar 2, 2009

$$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)$$