Simplifying nested summations for a function

[SpiffyEh]

Homework Statement

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.

Homework Equations

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?

 

[Mark44]

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.

 

[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

 

[Mark44]

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

 

[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?

 

[SpiffyEh]

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

 

[gabbagabbahey]

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

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

 

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

 

[gabbagabbahey]

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.

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

 

[SpiffyEh]

I've never heard of manipulating summations by index subsiutions

 

[gabbagabbahey]

I've never heard of manipulating summations by index subsiutions

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}

 

[SpiffyEh]

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

 

[gabbagabbahey]

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

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?

 

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

 

[gabbagabbahey]

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

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

 

[SpiffyEh]

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

 

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

 

[gabbagabbahey]

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

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)