Solving Recurrence Equations for Algorithm Analysis

[kaalen]

Homework Statement

I need to solve a recurrence equation in order to perform algorithm analysis. I got the recurrence from the algorithm I developed. It's been years since I did my undergrad degree and my maths is rusty.

Homework Equations

T(n)= 1+ \sum_{i=1}^n2(n-i+T(i))

The Attempt at a Solution

This is how far I got:
T(n)= 1+ \sum_{i=1}^n(2n-2i+2T(i))
T(n)= 1+ 2\sum_{i=1}^nn-2\sum_{i=1}^ni+2\sum_{i=1}^nT(i)
T(n)= 1+ 2n^2-2\frac{n(n+1)}{2}+2\sum_{i=1}^nT(i)
T(n)= 1+ n^2-n+2\sum_{i=1}^nT(i)

I'm not sure what to do with that T(i) in the sum. I tried this:
T(n)= 1+ n^2-n+2\frac{T(n)(T(n)+1)}{2}
T(n)= 1+ n^2-n+T(n)T(n)+T(n)

But what do I do with that T(n)T(n)? Can it be further simplified?
Can I say T(n)T(n)=T^2(n) or T(n)T(n)=T(n^2)

When I'm done simplifying I need to apply substitution, recursion tree or master theorem method to finish it off.

 

[susskind_leon]

Forget your approach T(n)= 1+ n^2-n+2\frac{T(n)(T(n)+1)}{2} That doesn't work!
Instead, rewrite T(n) as
T(n) = -1 -n^2 + n - 2 \sum_{i=1}^{n-1} T(i)
Then start with T(1):
T(1) = -1 - 1^2 + 1 = -1
Now
T(2) = -1 - 2^2 + 2 - 2 * ( -1 -1^2 + 1)
Now
T(3) = -1 - 3^2 + 3 - 2 * ( -1 - 2^2 + 2 - 2 * (-1 - 1^2 + 1))
T(3) = - 1 - 3^2 + 3 + (-2) * (-1 - 2^2 + 2) + (-2)^2 * (-1 - 1^2 + 1)
T(3) = -1 + (-2) * (-1) + (-2)^2 * (-1) - 3^2 + (-2) * (-2^2) + (-2)^2 * (-1^2) + 3 + (-2) * 2 + (-2)^2 * 1
Do you see the pattern? For T(n), you get
T(n) = - \sum_{i=0}^{n-1} (-2)^i - \sum_{i=0}^{n-1} (n-i)^2 (-2)^i + \sum_{i=0}^{n-1} (n-i) (-2)^i
Now, all you need to do is look up the partial sums, e.g. here http://en.wikipedia.org/wiki/List_of_mathematical_series#Power_series and use you favorpite CAS software to simplify the expressions. Good luck!

 

[kaalen]

Forget your approach T(n)= 1+ n^2-n+2\frac{T(n)(T(n)+1)}{2} That doesn't work!
Instead, rewrite T(n) as
T(n) = -1 -n^2 + n - 2 \sum_{i=1}^{n-1} T(i)

Hmm... haven't even thought about it this way. Mighty thanks for opening my eyes. I have since realized I had to fix my recurrence a bit because the algorithm calls itself on input from 1 to n-1, rather than to n (it would be calling itself till infinity that way).
So the corrected equation is
T(n) = 1 -n+ n^2 + 2 \sum_{i=1}^{n-1} T(i)
Few minutes ago I fed the numbers in and am now trying to figure out what the pattern is.
I noticed one thing in your proposed solution though and am hoping you can shed some more light before I proceed

How did you get from T(n)= 1+ n^2-n+2\sum_{i=1}^{n}T(n) to
T(n) = -1 -n^2 + n - 2 \sum_{i=1}^{n-1} T(i). Prefixes seem to have magically changed from + to - and vice versa and you seemed to have corrected \sum_{i=1}^{n} to \sum_{i=1}^{n-1} before I even noticed it's wrong. Just a lapsus?

 

[susskind_leon]

Firstly, it's 1+ n^2-n+2\sum_{i=1}^{n}T(i) and not 1+ n^2-n+2\sum_{i=1}^{n}T(n).
T(n)= 1+ n^2-n+2\sum_{i=1}^{n}T(i)= 1+ n^2-n+2\sum_{i=1}^{n-1}T(i)+2T(n)
Then you substract the last term and you get
T(n) - 2 T(n) = -T(n) = 1+ n^2-n+2\sum_{i=1}^{n}T(i)
Then, you multiply by -1 and you finally get
T(n) = -1 -n^2 + n - 2\sum_{i=1}^{n}T(i)
Regards!