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: Simplifying nested summations for a function

  1. Sep 8, 2010 #1
    1. The problem statement, all variables and given/known data

    Consider the following code fragment.
    for i=1 to n/2 do
    for j=i to n-i do
    for k=1 to j do
    output ‘‘foobar’’
    Assume n is even. Let T(n) denote the number of times ‘foobar’ is printed as a
    function of n.
    (a) Express T(n) as three nested summations.
    (b) Simplify the summation. Show your work.


    2. Relevant equations



    3. The attempt at a solution
    I thin I understand a)
    I got:
    [tex]\sum (\sum (\sum output "foobar" ))[/tex]

    the sum bounds starting from the outside inward:
    i = 1 to n/2
    j = 1 to n-i
    k = 1 to j

    I'm not sure how to simplify this. Could someone please explain it to me?
     
  2. jcsd
  3. Sep 8, 2010 #2

    Mark44

    Staff: Mentor

    I would pick a value for n (an even integer), and then see what the code does. That might give you some insight into simplifiying the summation.
     
  4. Sep 9, 2010 #3
    i tried n=4

    i: 1 j: 1 k:1 foobar
    i: 1 j: 2 k:1 foobar
    i: 1 j: 2 k:2 foobar
    i: 1 j: 3 k:1 foobar
    i: 1 j: 3 k:2 foobar
    i: 1 j: 3 k:3 foobar
    i: 1 j: 4 k:1 foobar
    i: 1 j: 4 k:2 foobar
    i: 1 j: 4 k:3 foobar
    i: 1 j: 4 k:4 foobar
    i: 1 j: 5 k:1 foobar
    i: 1 j: 5 k:2 foobar
    i: 1 j: 5 k:3 foobar
    i: 1 j: 5 k:4 foobar
    i: 1 j: 5 k:5 foobar
    i: 1 j: 6 k:1 foobar
    i: 1 j: 6 k:2 foobar
    i: 1 j: 6 k:3 foobar
    i: 1 j: 6 k:4 foobar
    i: 1 j: 6 k:5 foobar
    i: 1 j: 6 k:6 foobar
    i: 1 j: 7 k:1 foobar
    i: 1 j: 7 k:2 foobar
    i: 1 j: 7 k:3 foobar
    i: 1 j: 7 k:4 foobar
    i: 1 j: 7 k:5 foobar
    i: 1 j: 7 k:6 foobar
    i: 1 j: 7 k:7 foobar
    i: 2 j: 1 k:1 foobar
    i: 2 j: 2 k:1 foobar
    i: 2 j: 2 k:2 foobar
    i: 2 j: 3 k:1 foobar
    i: 2 j: 3 k:2 foobar
    i: 2 j: 3 k:3 foobar
    i: 2 j: 4 k:1 foobar
    i: 2 j: 4 k:2 foobar
    i: 2 j: 4 k:3 foobar
    i: 2 j: 4 k:4 foobar
    i: 2 j: 5 k:1 foobar
    i: 2 j: 5 k:2 foobar
    i: 2 j: 5 k:3 foobar
    i: 2 j: 5 k:4 foobar
    i: 2 j: 5 k:5 foobar
    i: 2 j: 6 k:1 foobar
    i: 2 j: 6 k:2 foobar
    i: 2 j: 6 k:3 foobar
    i: 2 j: 6 k:4 foobar
    i: 2 j: 6 k:5 foobar
    i: 2 j: 6 k:6 foobar
    i: 3 j: 1 k:1 foobar
    i: 3 j: 2 k:1 foobar
    i: 3 j: 2 k:2 foobar
    i: 3 j: 3 k:1 foobar
    i: 3 j: 3 k:2 foobar
    i: 3 j: 3 k:3 foobar
    i: 3 j: 4 k:1 foobar
    i: 3 j: 4 k:2 foobar
    i: 3 j: 4 k:3 foobar
    i: 3 j: 4 k:4 foobar
    i: 3 j: 5 k:1 foobar
    i: 3 j: 5 k:2 foobar
    i: 3 j: 5 k:3 foobar
    i: 3 j: 5 k:4 foobar
    i: 3 j: 5 k:5 foobar
    i: 4 j: 1 k:1 foobar
    i: 4 j: 2 k:1 foobar
    i: 4 j: 2 k:2 foobar
    i: 4 j: 3 k:1 foobar
    i: 4 j: 3 k:2 foobar
    i: 4 j: 3 k:3 foobar
    i: 4 j: 4 k:1 foobar
    i: 4 j: 4 k:2 foobar
    i: 4 j: 4 k:3 foobar
    i: 4 j: 4 k:4 foobar

    i don't see where to go with it though
     
  5. Sep 9, 2010 #4

    Mark44

    Staff: Mentor

    I don't have time to double-check right now, but I don't think your output is correct. Your innermost loop (with k) should be cycling through values, then the middle loop (with j), and finally the outermost loop (with i).
     
  6. Sep 9, 2010 #5

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    I'd break things down starting with your inner loop (I'll use [itex]a[/itex] as a variable to represent the text "foobar" being outputted):

    [tex]\sum_{k=1}^{j}a[/tex]

    How many times does this loop count [itex]a[/itex] (output "foobar"), could you represent this by a simple product rather than a sum?
     
  7. Sep 9, 2010 #6
    it outputs it j times but can I just multiply j*a?
     
  8. Sep 9, 2010 #7

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    Exactly, so your innermost sum is just equal to [itex]j*a[/itex] (it outputs "foobar" [itex]j[/itex] times). Now how about your middle sum, what does

    [tex]\sum_{j=i}^{n-i}ja[/tex]

    simplify to?

    Hint: [tex]\sum_{m=1}^{N} m = \frac{N}{2}(N+1)[/tex] ... a well-known result you are hopefully familiar with
     
    Last edited: Sep 10, 2010
  9. Sep 9, 2010 #8
    I'm a little confused about that one, I don't understand how to simplify it. I didn't get the first sum because it just seemed odd to me to multiply an output by j, i didn't tink I could do that.
     
  10. Sep 9, 2010 #9

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    Well, I suppose you should really just have "1" instead of "a", since your nested summation simply counts the number of times an action (outputting "foobar" in this case) is performed. So your innermost sum is

    [tex]\sum_{k=1}^{j} 1=j[/tex]

    and it outputs "foobar" [itex]j[/itex] times.
    As for the second summation, are you familiar with manipulating summations by index substitutions? If so, try the substitution [itex]j=m+i-1[/itex]...
     
  11. Sep 9, 2010 #10
    I've never heard of manipulating summations by index subsiutions
     
  12. Sep 9, 2010 #11

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    Basically, if you have a sum like

    [tex]\sum_{j=a}^{b} a_j[/tex]

    you might like to manipulate the sum so that it sums over a different index starting from 1 or zero instead of from [itex]a[/itex]. To do that, you make a substitution like [itex]j=m+a-1[/itex] and your sum becomes:

    [tex]\sum_{m+a-1 = a}^{m+a -1 = b} a_{m+a-1} = \sum_{m=1}^{m=1+b-a} a_{m+a-1}[/tex]
     
  13. Sep 9, 2010 #12
    so, [tex]\sum_{m=1}^{n-m-i+1} a(m+i-1) [/tex]? Or am I doing it wrong?
     
  14. Sep 9, 2010 #13

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    Close, but your upper limit on the summation is incorrect. If the upper limit on [itex]j[/itex] is [itex]n-2[/itex], and [itex]j=m+i-1[/itex], then at the upper limit you have [itex]m+i-1=n-i[/itex], which simplifies to [itex]m=n-2i+1[/itex], giving you the upper limit on your new index [itex]m[/itex].

    [tex]\sum_{j=i}^{n-i}j=\sum_{m=1}^{n-2i+1}(m+i-1)[/tex]

    ...follow?
     
  15. Sep 9, 2010 #14
    Oh ok, I see. So, at this point there are still two summations, I don't see how that made it any simpler though.
     
  16. Sep 9, 2010 #15

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    Well, since addition is commutative [it doesn't matter which order you add terms together in, i.e. 1+2+3 = (1+2)+3=1+(2+3)], you can now split the 2nd innermost/outermost summation into 2 (or 3 if you like) easy to compute summations:

    [tex]\sum_{m=1}^{n-2i+1}(m+i-1)= \sum_{m=1}^{n-2i+1}(i-1)+\sum_{m=1}^{n-2i+1}m[/tex]

    You already know how to compute the first one, and you should be able to use the hint I gave earlier to compute the 2nd one...
     
  17. Sep 9, 2010 #16
    Would the second one just be m(n-2i+1)?
     
  18. Sep 9, 2010 #17
    if you get back on to reply could you please show me how to finish this one up? I have a quiz on the subject tomorrow afternoon and i really want to understand how it works out.
     
  19. Sep 10, 2010 #18

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    No, you are summing over [itex]m[/itex], so it shouldn't appear in the result of your summation. Use the hint given in post # 7

    Edit: I just realized that the hint I gave contained a typo, I corrected post #7 (the [itex]m[/itex] in the result should have been [itex]N[/itex])
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook