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

-
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. – J. M. Feb 11 '12 at 1:14
@J.M. I'm aware that is the convention. "Meaningless" was a poor choice of wording on my part. My intention was just to ensure that there wasn't a typo or anything mixed in there. – Kurtis Zimmerman Feb 11 '12 at 1:47

$\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$

-
Ok, that makes sense. Is there some sort of closed form formula for something like that? – Michael Schilling Feb 11 '12 at 1:17
@MichaelSchilling, What do you mean by closed form formula? – NoChance Feb 11 '12 at 1:19
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$ – NoChance Feb 11 '12 at 1:22