Need help in solving a recurrence relation

[Constantinos]

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$_{k,k}$ = $\overline{c}$a$_{k,k-1}$+$\overline{c}$a$_{k-1,k}$+c$^{2}$a$_{k-1,k-1}$-$\overline{c}$$^{3}$a$_{k-1,k-2}$-$\overline{c}$$^{3}$a$_{k-2,k-1}$+($\overline{c}$-c)$\overline{c}$$^{2}$a$_{k-2,k-2}$+y((k,k))

with initial conditions:

a$_{n,0}$ = n $\forall$ n
and
a$_{0,n}$ = n $\forall$ n

and a,y:$N$X$N$→ℝ

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$_{k1,k2}$ : k1≤k, k2≤ k )

What methods do I have to study to solve that?

 

[Constantinos]

oh and $\overline{c}$+c = 1

 

[Ray Vickson]

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$_{k,k}$ = $\overline{c}$a$_{k,k-1}$+$\overline{c}$a$_{k-1,k}$+c$^{2}$a$_{k-1,k-1}$-$\overline{c}$$^{3}$a$_{k-1,k-2}$-$\overline{c}$$^{3}$a$_{k-2,k-1}$+($\overline{c}$-c)$\overline{c}$$^{2}$a$_{k-2,k-2}$+y((k,k))

with initial conditions:

a$_{n,0}$ = n $\forall$ n
and
a$_{0,n}$ = n $\forall$ n

and a,y:$N$X$N$→ℝ

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$_{k1,k2}$ : 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 $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.$ Then, if we know $f_1(z)$ and $f_2(z)$ we can get $f(z)$, and we can then "invert" to get the a_k,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 a_i,j for i ≠ j. For example, we would get something very different if we have a_k,j = a_j,k = 0 for 1 ≤ j ≤ k-1, vs. a_k,j = a_j,k = k for 0 ≤ j ≤ k, etc.

RGV

 

[Constantinos]

You could try a z-transform, or a generating function. Let $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.$ Then, if we know $f_1(z)$ and $f_2(z)$ we can get $f(z)$, and we can then "invert" to get the a_k,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 a_i,j for i ≠ j. For example, we would get something very different if we have a_k,j = a_j,k = 0 for 1 ≤ j ≤ k-1, vs. a_k,j = a_j,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...