Solve a set of inter-related recurrence relations

Question

T(n) = R(n-1) + n log n
R(n) = T(n-1) + n^2

Answer 1

Given R(n) = T(n-1) + n^2 

so, R(n-1) = T(n-2) + (n-1)^2

T(n)= T(n-2) + (n-1)^2+nlogn
T(n) = n^2 + (n-1)^2 + (n-2)^2...

The sum of squares of k numbers is k(k+1)(2k+1)/6  which is order of k^3

Hence T(n) = n^3

Comments

Some of the math terms seem to be slightly off in the beginning, other than that it looks fine.

Answer 2

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

Since n*logn is asymptotically compared to (n-1)^2

T(n)=T(n-4)+(n-1)^2+(n-3)^2

T(n)= c+(n-1)^2 + (n-3)^2 + ... [ where c is constant]

T(n)= O(n^3)

Now R(n)= R(n-2) + n^2 + (n-1)*log(n-1)

Since n*logn is asymptotically smaller compared to n^2

R(n) = R(n-2) + n^2

R(n) = n^2 + (n-2)^2 + (n-3)^2 + ....

R(n)= O(n^3)

Hence T(n) = Theta(R(n))

Answer 3

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

R(n) = R(n-2) + (n-1) log(n-1) + n^2

solving T(n): we get T(n) = n^2 log n

solving R(n): we get R(n) = n^3