1. Limited time only! Sign up for a free 30min personal 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!

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


    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]


    [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


    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