# Homework Help: Another summation problem

1. Nov 30, 2004

### EvLer

Hello, I really trying to understand what is going on with these summations.
the code is following:
Code (Text):

for p = 2 to n
for i = 1 to n - p + 1
j = i + p -1
for k = i to j - 1
O(1) + O(1)

Does j enter anywhere here besides the upper bound of the inner-most summation?
Here is what I have so far
Code (Text):

n     n-p+1    j-1
Sigma  Sigma    Sigma(C) = Sigma  (C) Sigma (j-1-i) = ...
p=2    i=1      k=i

then I break up the double sums on sums of j, -1, and i.

In the course of my attempt to solve this thing, I cannot get rid of j, while the expression is supposed to be in terms of n.
How do I get around it?

Thanks a lot.

2. Dec 1, 2004

3. Dec 1, 2004

### EvLer

Even with that, I still have j and cannot get rid of it!!!

4. Dec 1, 2004

### shmoe

You have $$\sum_{p=2}^{n}\sum_{i=1}^{n-p+1}\sum_{k=i}^{j-1}C$$ right?

Stick in j=i+p-1, which is assigned before your 3rd loop, and you get:

$$\sum_{p=2}^{n}\sum_{i=1}^{n-p+1}\sum_{k=i}^{i+p-2}C$$

No more j.