Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

2-index recurrence relations

  1. Feb 28, 2009 #1
    Is there a general method for solving 2-index recurrence relations with constant coefficients? Here is one I would like to solve

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

    with initial conditions

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

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

    thanks :)
  2. jcsd
  3. Mar 1, 2009 #2

    Sounds like you're on the right track. What expression did you get for the inhomogeneous part of the solution?
  4. Mar 1, 2009 #3
    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 [tex]a_{m,0} = m/x, a_{0,n} = n/y[/tex].
  5. Mar 1, 2009 #4
    Sounds right so far. What does the general solution look like before matching the boundary conditions?
  6. Mar 1, 2009 #5
    Substituting in M_mN_n for the homogeneous solution gives

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

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

    Putting it all together gives

    [tex]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[/tex]

    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
  7. Mar 1, 2009 #6
    Should that be

    [tex]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}[/tex]
  8. Mar 1, 2009 #7

    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.
  9. Mar 1, 2009 #8
    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?
  10. Mar 1, 2009 #9
    In the meantime, I found another method of doing it by searching online. The idea is to use a generating function

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

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

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

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

    [tex]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)}[/tex]

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

    [tex]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.

    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
  11. Mar 1, 2009 #10
    The argument looks right - Z-transform is the same idea. The generating function won't give [tex]a_{0,n}[/tex] 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 [tex]a_{m,n}[/tex] because it gives indeterminate values for m=1 and n=1.
  12. Mar 2, 2009 #11
    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
  13. Mar 2, 2009 #12
    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:

    [tex]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
  14. Mar 2, 2009 #13
    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).
  15. Mar 2, 2009 #14
    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

    [tex]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)[/tex]

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook