# How do I solve this double summation?

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

Not totally sure how to get passed this one. I brought it down from a triple to a double, but I'm having trouble with the fact that $i$ is the what is being added.

My thought is that it will be $\sum_{i=0}^{n} (i+1)^2$ but I cant say that with total certainty.

Thanks for the help.

-
Not sure how to use the summation symbol, I just kind of copied off a different one I saw. –  Michael Schilling Feb 11 '12 at 1:01
Your summation is not well defined. Notice that the outside summation index starts at $i = 0$, but the inside summation is defined from $j = 0$ to $j = i - 1$, which in this case would mean the summation indexes from $0$ to $-1$, which is meaningless as far as I know. –  Kurtis Zimmerman Feb 11 '12 at 1:06
ok, is there a closed form formula for something like that? –  Michael Schilling Feb 11 '12 at 1:06
I'm doing algorithm analysis for a computer science class.I guess that doesn't really make much sense. I can just change a couple of variables here and there to make the loops run from j=1 to i, instead of j=0 to <i –  Michael Schilling Feb 11 '12 at 1:07
@Kurtis: the convention is that empty sums (that is, lower index > upper index) are zero. So the formula's actually quite fine. –  Ｊ. Ｍ. Feb 11 '12 at 1:14

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

is composed of tow sums. Let's figure the inner sum first:

$\sum_{j=0}^{i-1} (i+1) = (i+1)(i-1-0+1) = (i+1)(i)$

Now you can evaluate the outer sum:

$\sum_{i=0}^{n} (i+1)(i)$ which is: $\sum_{i=0}^{n} i^2+i$

You can split the summs as:

$\sum_{i=0}^{n} i^2$ + $\sum_{i=0}^{n} i$

Or one like this: $\sum_{i=0}^{n} i^2$ –  Michael Schilling Feb 11 '12 at 1:19
Maybe that the wrong terminology. How $\sum_{i=0}^{n}$ i = (n(n+1))/2 –  Michael Schilling Feb 11 '12 at 1:20
@MichaelSchilling, if you check the link at the end of the post, you will find the formula for summing $i^2$ –  Emmad Kareem Feb 11 '12 at 1:22