1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Need help in solving a recurrence relation

  1. Jan 24, 2012 #1

    I was trying to find the expected time an algorithm takes to solve a certain problem, and I ended up in a very nasty recurrence relation of this form:

    a[itex]_{k,k}[/itex] = [itex]\overline{c}[/itex]a[itex]_{k,k-1}[/itex]+[itex]\overline{c}[/itex]a[itex]_{k-1,k}[/itex]+c[itex]^{2}[/itex]a[itex]_{k-1,k-1}[/itex]-[itex]\overline{c}[/itex][itex]^{3}[/itex]a[itex]_{k-1,k-2}[/itex]-[itex]\overline{c}[/itex][itex]^{3}[/itex]a[itex]_{k-2,k-1}[/itex]+([itex]\overline{c}[/itex]-c)[itex]\overline{c}[/itex][itex]^{2}[/itex]a[itex]_{k-2,k-2}[/itex]+y((k,k))

    with initial conditions:

    a[itex]_{n,0}[/itex] = n [itex]\forall[/itex] n
    a[itex]_{0,n}[/itex] = n [itex]\forall[/itex] n

    and a,y:[itex]N[/itex]X[itex]N[/itex]→ℝ

    I have no idea where to even begin! I've never encountered such a thing before, and it is actually a simpler version of a relation involving the full history of the recurrence relation(i.e all of the terms a[itex]_{k1,k2}[/itex] : k1≤k, k2≤ k )

    What methods do I have to study to solve that?
  2. jcsd
  3. Jan 24, 2012 #2
    oh and [itex]\overline{c}[/itex]+c = 1
    Last edited: Jan 24, 2012
  4. Jan 24, 2012 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You could try a z-transform, or a generating function. Let [itex] f(z)=\sum_{k=0}^{\infty} a_{k,k} z^k, \;\; f_1(z) = \sum_{k} a_{k-1,k,k} z^k, \;\mbox{ and } f_2(z) = \sum_{k} a_{k,k-1} z^k. [/itex] Then, if we know [itex] f_1(z)[/itex] and [itex] f_2(z) [/itex] we can get [itex] f(z)[/itex], and we can then "invert" to get the ak,k. Note, however, that we must know f_1 and f_2, and that means we do not have enough information to solve the problem: we need to know something about ai,j for i ≠ j. For example, we would get something very different if we have ak,j = aj,k = 0 for 1 ≤ j ≤ k-1, vs. ak,j = aj,k = k for 0 ≤ j ≤ k, etc.

  5. Jan 24, 2012 #4

    I'll try Z transforms then and see what I get. Also, I'll try to get a recurrence relation for a general a_i_j for any i,j, not just i=j=k. Also it holds that a_i_j = a_j_i for all i,j but I don't know if that helps...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook