Some useful closed forms to know.

Posted on 27.01.2012

So as promised, I'm using my blog to keep track of things I pick up and need to remember.

Todays mathematics is to calculate closed forms for the following sums:

$\sum_{k=1}^n k$ should be known simply to any student of Maths. If not, there's a simple argument for it - take $1+2+3+\ldots+n-1+n$ and reverse the series $n + n-1 + \ldots + 3 + 2 +1$. Now, observe that if you add each term of those series, you get $(1+n) + (2+n-1) + (3+n-2) + \ldots (n-1+2) + (n+1) = n(n+1)$. Almost there, except we've added each term twice and so most half the result. So $$\sum_{k=1}^n k = \frac{n}{2}(n+1)$$

Now for $\sum_{k=1}^n k^2$. Well, I found one simple proof of this that asks us to consider $k^3$. The source for this is here, credit goes to Dr Schwa of mathforum. If we compare $1, 8, 27, \ldots, n^3$ to $0, 1, 8, \ldots, (n-1)^3$ we note two things:

We can set these sums equal to each other, since $\sum_{k=1}^{n} k^3 - \sum_{k=0}^{n} k^3 = \sum_{k=1}^{n} (k^3 - (k-1)^3)$. So now:

$$\sum_{k=1}^{n} (k^3 - (k-1)^3) = n^3$$

Now $(k^3 - (k-1)^3) = 3k^2 -3k + 1$ so:

$$3\sum_{k=1}^{n}k^2 - 3\sum_{k=1}^{n}k + \sum_{k=1}^{n}1 = n^3$$

This is looking more like it. So now we have: $3\sum_{k=1}^{n}k^2 = n^3 - n + \frac{3n}{2}(n+1)$ since we can substitute the sum for $k$ and $1$ summed $n$ times is trivial. So then $\sum_{k=1}^{n}k^2 = \frac{n}{6}(2n^2 - 2 + 3(n+1)) = \frac{n}{6}(2n^2 + 3n + 1)$. The quadratic $2n^2 + 3n + 1 = (2n + 1)(n+1)$ which gives us, after all that:

$$\sum_{k=1}^{n}k^2 = \frac{n}{6}(n+1)(2n+1)$$

Finally for $\sum_{k=1}^{n} k^3$. I'll adapt the proofwiki bottom proof for this - we know that $\sum_{k=1}^{n} k^3 = 1^3 + 2^3 + \ldots + (n-1)^3 + n^3 = \sum_{k=0}^{n-1}(n-k)^3$. Expanding that last sum, $\sum_{k=1}^{n} k^3 = \sum_{k=0}^{n-1}(n^3 - k^3 + 3nk^2 - 3n^2k)$.

The intermediate step here took me a moment to notice. Observe that $\sum_{k=0}^{n-1}(n^3 - k^3 + 3nk^2 - 3n^2k) = n^3\sum_{k=0}^{n-1}1 - \sum_{k=0}^{n-1}k^3 + 3n\sum_{k=0}^{n-1}k^2 -3n^2\sum_{k=0}^{n-1}k$. So now:

$$\sum_{k=1}^{n} k^3 = n^4 + \frac{3n^2}{6}(n+1)(2n+1) - \frac{3n^3}{2}(n+1) - \sum_{k=0}^{n-1}k^3$$

Which simplifies to $\sum_{k=1}^{n} k^3 = n^4 + \frac{n^2}{2}(2n^2 +3n +1) - \frac{3n^3}{2}(n+1) - \sum_{k=0}^{n-1}k^3$ and again to $\sum_{k=1}^{n} k^3 = n^4 + \frac{n^2}{2}((2n^2 +3n +1) - 3n^3(n+1)) - \sum_{k=0}^{n-1}k^3$ and again to: $\sum_{k=1}^{n} k^3 = n^4 + \frac{1}{2}(2n^4 + 3n^3 + n^2 - 3n^4 -3n^3) - \sum_{k=0}^{n-1}k^3$.

This we can reduce to: $\sum_{k=1}^{n} k^3 = n^4 + \frac{1}{2}(n^2-n^4) - \sum_{k=0}^{n-1}k^3$ which can be shortened yet further: $\sum_{k=1}^{n} k^3 = \frac{1}{2}(n^4 + n^2) - \sum_{k=0}^{n-1}k^3$.

The final step, then, is to add $\sum_{k=1}^{n} k^3$ to both sides? Why? Well, we observed a bit further back that $\sum_{k=1}^{n} k^3 - \sum_{k=0}^{n} k^3 = n^3$ so here $2\sum_{k=1}^{n} k^3 = \frac{1}{2}(n^4 + n^2) + \sum_{k=1}^{n} k^3 - \sum_{k=0}^{n-1}k^3$ gives us $2\sum_{k=1}^{n} k^3 = \frac{1}{2}(n^4 + n^2) + n^3$. We now simply need to reduce this algebraically - $2\sum_{k=1}^{n} k^3 = \frac{1}{2}(n^4 + 2n^3 + n^2)$ combines the $n^3$, then factor out $n^2$: $2\sum_{k=1}^{n} k^3 = \frac{n^2}{2}(n^2 + 2n + 1)$. Finally, we observe that $n^2 + 2n + 1 = (n+1)^2$ and that we can divide through by two to give:

$$\sum_{k=1}^{n} k^3 = \frac{n^2}{4}(n+1)^2$$

That's enough fun for one evening