How to multiply (simplify?) two or more Riemann sums?

Question

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

I am studying The Algorithm Design Manual, so I have access to the process of simplification from http://www.algorist.com/algowiki/index.php/TADM2E_2.1. But I don't understand how each step leads to the next.

The first part of the of the answer from that page is:

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

That makes sense. Repeatedly summing "1" from 1 to j is just j. I can reason that.

But the next step is listed as:

$$\sum_{i=0}^{n-1}\ \biggl(\sum_{j=1}^nj\ - \sum_{j=1}^ij \biggr)$$

And that's where my reasoning starts to fall apart. What is going on and where should I look to learn more about this? Google searches for "how to multiply Riemann sums" and similar phrases return almost nothing related to this.

Thanks!

Answer 1

These are sums, not Riemann sums, so your searches are probably leading you astray. Also, you are not multiplying anything, you are nesting sums. You want to manipulate sums.

One random Google hit for "manipulating sums" is

Bayer, Rob, "Series Manipulation and Finding Sums", 06 August, 2010.

It seems like a reasonable place to start. The step you were stopped by is the third bullet there, "Adding/subtracting missing terms".

Many more examples are on the English Wikipedia page for Summation. The step you were stopped by is the variant immediately following "splitting a sum".

Answer 2

Reasoned my way a little further.

The sum of j from i+1 to n is going to be less than the sum of j from 1 to n. This is because you're starting at i+1 rather than 1, therefore you're not including the sums of j from 1 to i.

So if you sum everything from 1 to n, how much extra did you sum? You need to subtract the sums of j from 1 to i.

That's why:

$$\sum_{j=i+1}^nj = \left (\sum_{j=1}^nj - \sum_{j=1}^ij \right)$$

The rest of the formula uses the fact that a sequence of 1 + 2 + ... + n is equal to n * (n + 1) / 2 https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF