Recursive Equation

[Lordofnazgul]

Hello! i'm from Italy, and i'm trying to solve this equation:



T(n) = T(n - 1) + T(n - 2) + n

my result is that the big theta notation of this equation is Θ(2^n) and the big O notation is O(2^n) * (n)

but i think that i made something wrong. Can someone explain me how to calculate the tree main landau symbols of this equation? (O, Ω and Θ)? i need some help because i have the test not too far away. Thank you!

[nuzzle]

Salve!

Have you managed to solve the equation or have you been using some other procedure to get at the complexity measures you're suggesting?

[Lordofnazgul]

Salve!

Have you managed to solve the equation or have you been using some other procedure to get at the complexity measures you're suggesting?

Hello!
i have uploaded here how i made the exercise:


http://rapidshare.com/files/369564403/08.PDF.html

what do you think about it??
thank you!

[nuzzle]

what do you think about it??

I haven't worked much with recurrance relations and I was hoping to be able to solve this one formally but unfortunately I haven't been very successful.

Regarding your solution it looks like you've come up with a Fibonacci tree but that corresponds to only this part of the equation doesn't it?

T(n) = T(n - 1) + T(n - 2)

What I do know is that a Fibonacci tree grows almost as fast as a binary three corresponding to this equation,

T(n) = T(n - 1) + T(n - 1) = 2*T(n-1)

And both have exponential growth so it should be O(c^n) for both.

The question is what happens when you add the n term? I have been able to solve this,

T(n) = 2*T(n-1) + n

and according to my results the dominant term becomes 3*2^n when n grows big. This also means your equation has exponential growth too (because it's bound between two equations with exponential growth), like

T(n) = T(n - 1) + T(n - 2) (lower bound)
T(n) = T(n - 1) + T(n - 2) + n (your equation)
T(n) = 2*T(n-1) + n (upper bound)

So I'm pretty sure Big-O for your equation is O(c^n). I come back if I manage to actually solve it. The problem I'm having is that when I solve it as a second order difference equation the solution I get doesn't correspond to the values you expect when you use the formula as a recurrence relation. I'll try to figure out why this is so.

[superbonzo]

this sort of linear recursive equation are usually solved by summing their z transforms:

sum{n,2,+inf} T[n]/z^n = sum{n,2,+inf} T[n-1]/z^n + sum{n,2,+inf} T[n-2]/z^n + sum{n,2,+inf}n/z^n

then, we have

sum{n,2,+inf} T[n-1]/z^n = ( T[1]/z + sum{n,2,+inf} T[n]/z^n ) / z

and

sum{n,2,+inf} T[n-2]/z^n = ( T[0] + T[1]/z + sum{n,2,+inf} T[n]/z^n ) / z^2

and

sum{n,2,+inf}n/z^n = sum{n,1,+inf}n/z^n - 1/z = z/(z-1)^2 - 1/z

therefore

sum{n,2,+inf} T[n]/z^n ( 1 - 1/z - 1/z^2 )= T[1]/z^2 + T[0]/z^2 + T[1]/z^3 + z/(z-1)^2 - 1/z

that is ( calling A:=T[0] and B:=T[1] for clarity )

sum{n,0,+inf} T[n]/z^n = A + B/z + ( (A+B)/z^2 + B/z^3 + z/(z-1)^2 - 1/z ) / ( 1 - 1/z - 1/z^2 )

finally, the not difficult but very boring part: we need to calculate the Laurent expansion of the right hand side... I have no time at the moment, so I simply computed the expansion in Wolfram Mathematica; it gives me

((1/2 (1 - Sqrt[5]))^n (-5 + 3 Sqrt[5] + A + Sqrt[5] A - 2 B) + (1/2 (1 + Sqrt[5]))^n (5 + 3 Sqrt[5] + (-1 + Sqrt[5]) A + 2 B))/(2 Sqrt[5]) - n - 3

which seems correct (of course A,B,n integers and n>=2 ). Indeed, as nuzzle said, it's O(c^n).

[Lordofnazgul]

wow thank you to both of you! the only thing is that i have never made the z-transforms and they seems a little bit complicated! i would try to solve them with an easier method, but i don't understand how i can do... because the other exercises that my teacher gave us were much easier, but this one is more difficult... isn't there another way to solve them?? for example with the tree (as i did in the file i posted), or just substitution would be better! thank you!

[superbonzo]

isn't there another way to solve them??

well, the z transform is the most systematic way of solving these equations (more specifically, when you'll study a bit of complex analisys you'll immediately recognize that the "n" term in your recurrence equation add an holomorphic term to the z transform; this basically means that the result can be "somehow" computed this way ... )

but there are certainly other ways of solving it. For example, you can "linearize" your recurrence equation by representing the recurrence step as a linear operator in a suitable vector space. Then, the problem essentially reduces to a matrix diagonalization
(an hint: how does the quadruple (T[n+1],T[n],n,1) get transformed by the recurrence step ? ).

[huseyinaksu26]

Hi everybdoy ı need your help about recursion algorithm in mathematica.
Question is ı could not get any result when ı coded below equation. it is not stoping.

Equation is

S[n1_,n2_,p_,t_]:=n1/(2*n1-1)(S[n1-1,n2,p,t]-(n1-1)S[n1-2,n2,p,t])-n2/(2*n2-1)(S[n1,n2-1,p,t]-(n2-1)S[n1,n2-2,p,t])

here the S[0,0,p,t]=p*t (I just write simple one here)
-1<t<1
for examlple S[2,2,1,0.5]=?
can you code it in mathematica.
Thanks