Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help with summations code

  1. Nov 24, 2004 #1
    Hi everyone,
    I have the following recurrence to represent in terms of n:
    Code (Text):

      n-1    n      j
    Sigma Sigma Sigma(c1) =...
     i =1  j = i+1 k=1
     
    Basically, it is an analysis of following code:
    Code (Text):

    for(i = 1 to n -1)
       for(j = i+1 to n)
           for(k = 1 to j)
          something of O(1)
     
    So, I came up with summations but not sure how to switch to n.
    So far I have following:
    Code (Text):

     n-1    n                    n-1    n            n-1      n      
    Sigma Sigma (c1)(j-1) = c1 Sigma Sigma   j  - c1 Sigma Sigma 1;  
     i=1  j=i+1                 i=1   j=i+1          i=1   j=i+1    
     
    Second part resulted in c1[n(n-1) - [n(n+1)]/2 - (n-1)]; but I am stuck on the first part. Should I regard j = i + 1 as some constant?

    Thanks a lot.
     
    Last edited: Nov 24, 2004
  2. jcsd
  3. Nov 24, 2004 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    You shouldn't have "j - 1" you should just have j, i.e.

    [tex]\sum _{i = 1} ^{n - 1}\sum _{j = i + 1} ^n \sum _{k = 1} ^j c_1 = \sum _{i = 1} ^{n - 1}\sum _{j = i + 1} ^n jc_1[/tex]

    Now:

    [tex]\sum _{i = 1} ^{n - 1}\sum _{j = i + 1} ^n jc_1 = \sum _{i = 1} ^{n - 1}\left (\sum _{j = 1} ^n jc_1 - \sum _{j = 1} ^i jc_1\right ) = c_1 \sum_{i = 1} ^{n - 1}\left (\frac{n(n + 1)}{2} - \frac{i(i - 1)}{2}\right )[/tex]

    See if you can go from there.
     
  4. Nov 24, 2004 #3
    Thanks a lot for the reply.
    I have some questions on your solution though:
    how did you come up with i(i-1)/2 for the second expression in the parenthesis but n(n+1)/2 for the first? I know there is a minus before the i-expression but is it affecting the inner i-parenthesis?
    From where you left off, I am thinking of breaking off the summation into two: one dependent on n and other dependent on i, is this the right direction?

    Again, thank you very much.
     
  5. Nov 25, 2004 #4

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Sorry, that was just a typo. It should be n(n+1)/2, and i(i+1)/2. As for the rest, I'm sure you can figure out the right direction without me telling you.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook