# Homework Help: Simplifying nested summations for a function

1. Sep 8, 2010

### SpiffyEh

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:
$$\sum (\sum (\sum output "foobar" ))$$

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. Sep 8, 2010

### 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.

3. Sep 9, 2010

### SpiffyEh

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

4. Sep 9, 2010

### 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).

5. Sep 9, 2010

### gabbagabbahey

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

$$\sum_{k=1}^{j}a$$

How many times does this loop count $a$ (output "foobar"), could you represent this by a simple product rather than a sum?

6. Sep 9, 2010

### SpiffyEh

it outputs it j times but can I just multiply j*a?

7. Sep 9, 2010

### gabbagabbahey

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

$$\sum_{j=i}^{n-i}ja$$

simplify to?

Hint: $$\sum_{m=1}^{N} m = \frac{N}{2}(N+1)$$ ... a well-known result you are hopefully familiar with

Last edited: Sep 10, 2010
8. Sep 9, 2010

### SpiffyEh

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.

9. Sep 9, 2010

### gabbagabbahey

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

$$\sum_{k=1}^{j} 1=j$$

and it outputs "foobar" $j$ times.
As for the second summation, are you familiar with manipulating summations by index substitutions? If so, try the substitution $j=m+i-1$...

10. Sep 9, 2010

### SpiffyEh

I've never heard of manipulating summations by index subsiutions

11. Sep 9, 2010

### gabbagabbahey

Basically, if you have a sum like

$$\sum_{j=a}^{b} a_j$$

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

$$\sum_{m+a-1 = a}^{m+a -1 = b} a_{m+a-1} = \sum_{m=1}^{m=1+b-a} a_{m+a-1}$$

12. Sep 9, 2010

### SpiffyEh

so, $$\sum_{m=1}^{n-m-i+1} a(m+i-1)$$? Or am I doing it wrong?

13. Sep 9, 2010

### gabbagabbahey

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

$$\sum_{j=i}^{n-i}j=\sum_{m=1}^{n-2i+1}(m+i-1)$$

...follow?

14. Sep 9, 2010

### SpiffyEh

Oh ok, I see. So, at this point there are still two summations, I don't see how that made it any simpler though.

15. Sep 9, 2010

### gabbagabbahey

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:

$$\sum_{m=1}^{n-2i+1}(m+i-1)= \sum_{m=1}^{n-2i+1}(i-1)+\sum_{m=1}^{n-2i+1}m$$

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...

16. Sep 9, 2010

### SpiffyEh

Would the second one just be m(n-2i+1)?

17. Sep 9, 2010

### SpiffyEh

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.

18. Sep 10, 2010

### gabbagabbahey

No, you are summing over $m$, 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 $m$ in the result should have been $N$)