1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recurrence equation with sum

  1. Oct 16, 2011 #1
    1. The problem statement, all variables and given/known data
    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.

    2. Relevant equations
    [itex]T(n)= 1+ \sum_{i=1}^n2(n-i+T(i)) [/itex]


    3. The attempt at a solution
    This is how far I got:
    [itex]T(n)= 1+ \sum_{i=1}^n(2n-2i+2T(i)) [/itex]
    [itex]T(n)= 1+ 2\sum_{i=1}^nn-2\sum_{i=1}^ni+2\sum_{i=1}^nT(i) [/itex]
    [itex]T(n)= 1+ 2n^2-2\frac{n(n+1)}{2}+2\sum_{i=1}^nT(i) [/itex]
    [itex]T(n)= 1+ n^2-n+2\sum_{i=1}^nT(i) [/itex]

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

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

    When I'm done simplifying I need to apply substitution, recursion tree or master theorem method to finish it off.
     
  2. jcsd
  3. Oct 16, 2011 #2
    Forget your approach [itex]T(n)= 1+ n^2-n+2\frac{T(n)(T(n)+1)}{2}[/itex] That doesn't work!
    Instead, rewrite T(n) as
    [tex] T(n) = -1 -n^2 + n - 2 \sum_{i=1}^{n-1} T(i)[/tex]
    Then start with T(1):
    [tex] T(1) = -1 - 1^2 + 1 = -1 [/tex]
    Now
    [tex] T(2) = -1 - 2^2 + 2 - 2 * ( -1 -1^2 + 1) [/tex]
    Now
    [tex] T(3) = -1 - 3^2 + 3 - 2 * ( -1 - 2^2 + 2 - 2 * (-1 - 1^2 + 1)) [/tex]
    [tex] T(3) = - 1 - 3^2 + 3 + (-2) * (-1 - 2^2 + 2) + (-2)^2 * (-1 - 1^2 + 1) [/tex]
    [tex] T(3) = -1 + (-2) * (-1) + (-2)^2 * (-1) - 3^2 + (-2) * (-2^2) + (-2)^2 * (-1^2) + 3 + (-2) * 2 + (-2)^2 * 1 [/tex]
    Do you see the pattern? For T(n), you get
    [tex] 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 [/tex]
    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!
     
  4. Oct 16, 2011 #3
    Hmm... haven't even thought about it this way. Mighty thanks for opening my eyes. I have since realised 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
    [tex] T(n) = 1 -n+ n^2 + 2 \sum_{i=1}^{n-1} T(i)[/tex]
    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 [tex]T(n)= 1+ n^2-n+2\sum_{i=1}^{n}T(n)[/tex] to
    [tex] T(n) = -1 -n^2 + n - 2 \sum_{i=1}^{n-1} T(i)[/tex]. Prefixes seem to have magically changed from + to - and vice versa and you seemed to have corrected [tex]\sum_{i=1}^{n}[/tex] to [tex]\sum_{i=1}^{n-1}[/tex] before I even noticed it's wrong. Just a lapsus?
     
  5. Oct 17, 2011 #4
    Firstly, it's [itex]1+ n^2-n+2\sum_{i=1}^{n}T(i)[/itex] and not [itex]1+ n^2-n+2\sum_{i=1}^{n}T(n)[/itex].
    [tex]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)[/tex]
    Then you substract the last term and you get
    [tex] T(n) - 2 T(n) = -T(n) = 1+ n^2-n+2\sum_{i=1}^{n}T(i) [/tex]
    Then, you multiply by -1 and you finally get
    [tex] T(n) = -1 -n^2 + n - 2\sum_{i=1}^{n}T(i) [/tex]
    Regards!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook