Motivation
Suppose there are two people (\(A\) and \(B\)) in a room. How many unique ways are there to shake hands (if every one shakes hands with their right hand)? There is only way to do this and it is \(AB\) (note: that \(BA\) is the same thing!).
Now, suppose there are three people (\(A, B, \) and \(C\)) in a room. Now how many unique handshakes are there? We can list the three possible handshakes as \(AB\), \(AC\), and \(BC\). Another way to think about this is, suppose \(A\) has to shakes hands with everyone first, then \(B\) with everyone else, and then \(C\) with no one else. Thus, \(A\) shakes hands with two other people. \(B\) shakes hands with \(C\) because \(B\) already shook hands with \(A\) and \(C\) doesn’t have to do anything because she’s already shaken hands with everyone else. So, we can see that the total number of unique handshakes is $$2 + 1 + 0 = 3$$ where \(2\) represents the number of handshakes that \(A\) makes, \(1\) represents the number of handshakes that \(B\) makes, and \(0\) represents the number of handshakes that \(C\) makes.
Using this reasoning we can see that if there were \(N\) people in the room, the total number of handshakes would be $$(N-1) + (N-2) + \cdots + 1 + 0 = ?$$
Or in more condensed notation, $$\sum_{k=0}^{N-1}k = ?$$
Now, there are a lot of ways to evaluate the sum, but we can use some combinatorial reasoning to resolve this. If there are \(N\) people in a room and we want to know how many unique handshakes there are, it is a matter of answering
How many ways are there to pick two people from a set of \(N\)?
This question is neatly answered by $${N \choose 2} = \frac{N(N-1)}{2}$$
(Recall that \({N \choose K} = \frac{N!}{(N-K)!K!}\) and represents the number of ways to pick \(K\) objects from \(N\) without caring about the order in which those objects were picked.)
Thus, $$\sum_{k=0}^{N-1}k = {N \choose 2} = \frac{N(N-1)}{2}$$
Verify this for yourself!
Some Math
What is interesting is that we can express sums of integers through combinatorial functions. So, what can we do with this?
If we forget about the handshake context and maintain some curiosity in wanting to evaluate sums of integers, then let’s try our hand at finding out what $$\sum_{k=0}^{N}k^{2}$$ would be.
Here’s a nice little trick when we want to evaluate these types of sums.
First, we’ll just focus on \(k^{2}\) and then we’ll take care of the sum. Let’s rewrite \(k^{2}\) as $$k^{2} = k(k-1) + k$$
Notice that \(k(k-1) = 2!{k \choose 2}\) and \(k = 1!{k \choose 1}\). So, we have $$\sum_{k=0}^{N}k^{2} = \sum_{k=0}^{N}(k(k-1) + k) = \sum_{k=0}^{N}\Big(2!{k \choose 2} + 1!{k \choose 1}\Big)$$
So now it is a matter of evaluating \(\sum_{k=0}^{N}2!{k \choose 2}\) and \(\sum_{k=0}^{N}1!{k \choose 1}\). But, we already saw that $$\sum_{k=0}^{N-1}k = {N \choose 2}$$ So $$\sum_{k=0}^{N}1!{k \choose 1} = {N+1 \choose 2}$$ (notice that \(k = {k \choose 1}\) and that the upper index changed from \(N-1\) to \(N\)).
What about \(\sum_{k=0}^{N}2!{k \choose 2}\)? Well, it turns out (and I leave this as an exercise for the reader (I’ve always wanted to write that)) that \(\sum_{k=0}^{N}{k \choose r} = {N+1 \choose r+1}\) (where I use the convention that \({k \choose r} = 0\) for \(0 \leq k < r\)). And this tells us that $$\sum_{k=0}^{N}2!{k \choose 2} = 2!{N+1 \choose 3}$$ Putting this all together we see that $$\sum_{k=0}^{N}k^{2} = 2!{N+1 \choose 3} + {N+1 \choose 2}$$
A General Technique
To get a handle on a general technique for solving $$\sum_{k=0}^{N}k^{p}$$ with positive integer \(p\), let’s take a look at how to obtain a formula for $$\sum_{k=0}^{N}k^{3}$$
We’ll use a similar technique from the previous section, but now rewrite \(k^{3}\) as \(k^{3} = k(k-1)(k-2) + 3k^{2} – 2k\). Wrapping this in a summation we have $$\sum_{k=0}^{N}k^{3} = \sum_{k=0}^{N}\Big(k(k-1)(k-2) + 3k^{2} – 2k\Big)$$
What was the great wisdom in this you may ask? Well, now we recognize that \(k(k-1)(k-2) = 3!{k \choose 3}\) and we also recognize that we already have the result for \(\sum_{k=0}^{N}k^{2}\) and \(\sum_{k=0}^{N}k\). Therefore,
$$\begin{aligned}\sum_{k=0}^{N}k^{3} & = \sum_{k=0}^{N}\Big(k(k-1)(k-2) + 3k^{2} – 2k\Big)\\
& = \sum_{k=0}^{N}3!{k \choose 3} + 3\sum_{k=0}^{N}k^{2} -2\sum_{k=0}^{N}k\\
& = 3!{N+1 \choose 4} + 3\Bigg(2!{N+1 \choose 3} + {N+1 \choose 2}\Bigg) – 2{N+1 \choose 2}
\end{aligned}$$
We can always go ahead and tidy this up a bit, but that’s just busy work.
Now, what about \(\sum_{k=0}^{N}k^4\)? Just do the same thing that was done for \(\sum_{k=0}^{N}k^3\). Write $$\sum_{k=0}^{N}k^{4} = \sum_{k=0}^{N}\Big(k(k-1)(k-2)(k-3) + 6k^{3} – 11k^{2} + 6k\Big)$$
Recognize that \(k(k-1)(k-2)(k-3) = 4!{k \choose 4}\) and then: algebra.
Enjoy!