Need help in solving a recurrence relation

  • #1
Hey!

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
and
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?
 

Answers and Replies

  • #2
oh and [itex]\overline{c}[/itex]+c = 1
 
Last edited:
  • #3
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
Hey!

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

RGV
 
  • #4
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.

RGV
Thanks!

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

Related Threads on Need help in solving a recurrence relation

  • Last Post
Replies
3
Views
2K
Replies
8
Views
3K
  • Last Post
Replies
5
Views
3K
Replies
7
Views
702
Replies
4
Views
7K
Replies
1
Views
4K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
1K
Top