1
$\begingroup$

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

  • 0
    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.2012-02-11
  • 0
    ok, is there a closed form formula for something like that?2012-02-11
  • 0
    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 2012-02-11
  • 1
    @Kurtis: the convention is that empty sums (that is, lower index > upper index) are zero. So the formula's actually quite fine.2012-02-11
  • 0
    @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.2012-02-11

1 Answers 1

4

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

The following link may help you further: Some summations of polynomial expressions

  • 0
    Ok, that makes sense. Is there some sort of closed form formula for something like that?2012-02-11
  • 0
    @MichaelSchilling, What do you mean by closed form formula?2012-02-11
  • 0
    Or one like this: $\sum_{i=0}^{n} i^2$2012-02-11
  • 1
    Maybe that the wrong terminology. How $\sum_{i=0}^{n}$ i = (n(n+1))/22012-02-11
  • 0
    @MichaelSchilling, if you check the link at the end of the post, you will find the formula for summing $i^2$2012-02-11
  • 0
    Oh, ok. What about the $i^2 + i$ one though? Is it possible to spit those up into two summations? EDIT: ok, nevermind. I got it. thanks for the help!2012-02-11
  • 0
    Yes, I edited to post to show that.2012-02-11