I have a question about a formula describing a sum of partial sums. So, a partial sum is, famously:
$$k = \frac{n(n+1)}{2}$$
Now, I wanted to know how to write down the sum of this (up to the $n^{th}$ term):
$$\frac{n(n+1)}{2} + \frac{(n- 1)(n – 1+1)}{2} + \frac{(n- 2)(n – 2+1)}{2} \dots+ 1$$
The best thing i can come up with would be to include the summation notation:
$$\sum_{0}^{n}\frac{(n-i)(n-i+1)}{2}$$
Is there a way to simplify it further?
Naively, I though of substituting $$x = \frac{n(n+1)}{2}$$
and then doing $$\frac{(x)(x+1)}{2}$$ but it obviously doesn't work (I wrote a few lines of code to check it).
There's no particular point to it, I just wanted to familiarize myself with the notation.
Best Answer
There's a few ways to write this, depending on what you're looking for.
As you said, we have a formula for the partial sums
$$S_n = \sum_{k = 0}^n k = \frac{(n+1)n}{2}.$$
Then if you want the sums of these, say the first $N$ many, then you want
$$\sum_{n = 0}^N S_n = \sum_{n = 0}^N \sum_{k = 0}^n k.$$
As you've said, another way to write this is as
$$\sum_{n = 0}^N \frac{(n+1)n}{2}$$
Of course, we can simplify this to
$$\frac{1}{2} \left ( \sum_{n = 0}^N n^2 + \sum_{n=0}^N n \right )$$
(do you see why?), and these sums both have well known formulas, letting us finish off with
$$\sum_{n=0}^N \sum_{k=0}^n k = \frac{N^3}{6} + \frac{N^2}{2} + \frac{N}{3}.$$
As an aside, you might notice we summed $k$ twice and got something that looked cubic. If you know some calculus, you'll know that integrating $x$ twice will give $\frac{x^3}{6}$ plus some constant... which looks suspiciously similar to the $\frac{N^3}{6}$ that we got from the above sum.
It turns out this can be made precise with "finite calculus", as explained in Knuth, Grahm, and Patashnik's (excellent) Concrete Mathematics as well as in the (very well written) pdf here by David Gleich. This is a very useful technique for evaluating tricky sums like this, and if it sounds interesting, I recommend looking into it!
I hope this helps ^_^