Trying to find a formula for the following algorithm

Question

I am trying to make a formula for the following algorithm as a function of n, building up my answer using summations. The algorithm is:

sum := 0
for i := 1 to n do
    for j := 1 to i^2 do
        for k = 1 to j do
            sum++

So far, I have the following:

$$\sum_{i=1}^n\sum_{j=1}^{i^2}\sum_{k=1}^j1$$

After I simplify the far right summation, I get:

$$\sum_{i=1}^n\sum_{j=1}^{i^2}j$$

I am not quite sure what to do for the upper bound of $i^2$ for the middle summation. I thought perhaps $$\sum_{j=1}^{i^2}j=i^2(i^2+1)/2$$

But I don't think this is correct. And after simplifying the summation with $i^2$ upper bound, I am still confused on how to further simplify the entire triple summation. I appreciate any help.

Answer 1

Your intermediate answer seems correct. We then have

$\sum_{i=1}^n \frac{i^2 (i^2+1)}{2} = \frac{1}{2}\left( \sum_{i=1}^n i^4 + \sum_{i=1}^n i^2\right) $

And a little Googling or discrete will yield summation formulas for squares or fourth powers, and the final answer seems to be:

$ n^5/10 + n^4/4 + n^3/3 + n^2/4 + n^2/15$

Answer 2

I think you're fine through your summation of $i$ step. This leaves you with $$\sum_{i=1}^n \frac{i^4+i^2}{2} $$ You can now use standard sum formulas to finish off: $\sum_{i=1}^{n} i^4=\frac{6n^5+15n^4+10n^3-n}{30}$ and $\sum_{i=1}^{n} i^2=\frac{2n^3+3n^2+n}{6}$

For these sum formulas, see for instance http://mathworld.wolfram.com/PowerSum.html