Following in Gauss's footsteps : Computing the Sum of the First n Positive Integers

What if we want to compute the following sums for which $n$ is a positive integer. $$ \sum_{k=1}^{n} k = 1+2+3+\cdots+n $$ $$ \sum_{k=1}^{n} k^2 = 1^2+2^2+3^2+\cdots+n^2 $$ $$ \sum_{k=1}^{n} k^3 = 1^3+2^3+3^3+\cdots+n^3 $$ You can just power your way through it by brute forcing this sum, but for a large amount of $n$ this might become very difficult. Maybe there is something smarter we can do right? Well, the same thought went through Gauss’s head.

Gauss, the mathematical prodigy

Germany in the $1780$s, a bunch of children are sitting in a classroom. The teacher just gave the entire class the tedious assignment of summing the first $100$ integers. In other words, he wanted the children to compute: $$ \sum_{k=1}^{100} k = 1+2+3+\cdots+100 $$ The teacher hoped that this exercise would keep the kids busy for half an hour, but a young Gauss was quick to answer that the sum’s value is $5\,050$. This was only a glimpse of the pure genius of Gauss. However, he was no literal computer adding all the numbers in his head. He had an insight where brute forcing the computation was not needed. He had a deeper insight, what if you do the following? $$ S = 1 + 2+ 3 + \cdots +n$$ $$ S = n + n-1+ n-2 + \cdots +1$$ By adding the two sums, the following is obtained: $$ 2S = (n+1) + (n-1+2) + (n-2+3) + \cdots + (n+1)$$ $$ 2S = (n+1) + (n+1) + (n+1) + \cdots + (n+1)$$ There are $n$ terms of value $n+1$ in the right-hand side of the equation so this simplifies to: $$ S = \frac{n(n+1)}{2} $$ Applying this formula for $n=100$ indeed results in $5\,050$. Gauss would later go on to have many contributions in math and science. His name is widely regarded as one of the greats to ever practice the field. I can write multiple blog posts on his work which I might do in the future.

Extending the method

Now, what if we want to consider the sum of all squares? How can we do this? Well, consider $$ (k-1)^2 = k^2 \, – \, 2k + 1$$ Then the terms can be rearranged such that $$ k^2 - (k-1)^2 = 2k - 1$$ Taking the sum on both sides leads to $$ \sum_{k=1}^{n} k^2 - (k-1)^2 = \sum_{k=1}^{n} (2k \,–\, 1)$$ $$ 1^2 + (2^2 \, –\, 1^2) + (3^2\, –\, 2^2) + \cdots + (n^2\, – \, (n-1)^2) = n^2 = \sum_{k=1}^{n} (2k\, –\, 1) $$ The idea above also is known as telescoping, a method where intermediate terms cancel out in a sum or product, leaving only the last term. This simplifies the sum a lot. We can proceed by solving for $\sum_{k=1}^{n} k$, this leads to: $$ n^2 = \sum_{k=1}^{n} (2k) - n $$ $$ n^2 +n = 2 \sum_{k=1}^{n} k $$ $$ \frac{n(n+1)}{2} = \sum_{k=1}^{n} k $$ This is very nice and a different way of verifying our earlier result. However, can we extend this idea to compute the following sum for an arbitrary positive integer $m$? $$ \sum_{k=1}^{n} k^m = 1^m+2^m+3^m+\cdots+n^m $$ Well, we can start just simple by considering $m=2$. Then consider $$ (k-1)^3 = k^3 \,–\, 3k^2 + 3k - 1$$ Rearranging the expression leads to $$ k^3 \,– (k-1)^3 = 3k^2 - 3k + 1$$ Then taking the sum on both sides leads to $$ n^3 = \sum_{k=1}^{n} 3k^2 – \, \sum_{k=1}^{n}3k + \sum_{k=1}^{n} 1$$ $$ n^3 = \sum_{k=1}^{n} 3k^2 – \, \frac{3n(n+1)}{2} +\, n$$ Solving this equation leads to $$ 3 \left( \sum_{k=1}^{n} k^2 \right) = n^3 + \frac{3n(n+1)}{2} – \, n $$ $$ \sum_{k=1}^{n} k^2 = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n $$ $$ \sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$$ It is very nice to have this result because we can extend this idea to any $m$. Let’s see what happens if we consider $m=4$. Let's use the same idea from before. $$ (k-1)^4 = k^4 \, –\, 4k^3 + 6k^2 – 4k + 1 $$ Rearranging the expression leads to $$ k^4 - (k-1)^4 = 4k^3 - 6k^2 + 4k - 1 $$ Then taking the sum on both sides leads to $$ n^4 = 4 \sum_{k=1}^{n} k^3 – \sum_{k=1}^{n} 6k^2 + \sum_{k=1}^{n}4k - \sum_{k=1}^{n} 1 $$ $$ n^4 = 4 \sum_{k=1}^{n} k^3 – \, n(n+1)(2n+1) \, + 2n(n+1) - n $$ Solving this equation leads to $$ n^4 + 2n^3 + n^2= 4 \sum_{k=1}^{n} k^3 $$ $$ n^2(n^2 + 2n + 1)= 4 \sum_{k=1}^{n} k^3 $$ $$ n^2(n+1)^2= 4 \sum_{k=1}^{n} k^3 $$ $$ \frac{n^2(n+1)^2}{4}= \sum_{k=1}^{n} k^3 $$ Wait! This means that $$ \sum_{k=1}^{n} k^3 = \left(\sum_{k=1}^{n} k\right)^2 $$ This is a very nice result. Can we understand why this result is so nice? Well, let’s visualize what we just did.

Concluding with some nice visual proofs

All our earlier results can be easily understood with some visual proofs. Let’s start with our most simple case of $S = \sum_{k=1}^{n} k$.

Then one can obtain that $S = \frac{n(n+1)}{2}$. Let’s expand this idea to $S = \sum_{k=1}^{n} k^2$. For this example, we arrange the sum squares into some kind of pyramid. Then having obtained a pyramid, multiple pyramids can be shifted in a position so that the sum formula can be derived. A beautiful animation of this can be considered below:

However, we are not done yet. We still want to know why $ \sum_{k=1}^{n} k^3 = (\sum_{k=1}^{n} k)^2 $. This time, we start from $ \sum_{k=1}^{n} k^3$ by interpreting each term as the volume of a cube with length k. It turns out that we can arrange these terms in a 2D grid. Again, a beautiful illustration of this is shown in the video below:

It turns out that a square which has a side $S = \sum_{k=1}^{n} k$ can be partitioned into squares and half-squares whose areas add to cubes.

Unfortunately, we cannot really extend this idea for $m>3$. Things break down visually because $m=4$ corresponds to stacking hypercubes in four dimensions, $m=5$ in five, etc. It means that you can’t truly visualize these in Euclidean 3D space. However, you can algebraically generalize the geometric idea. Note that we always could extend our idea to any arbitrary $m$ using the formula $$ (k-1)^{m+1} = k^{m+1} + \cdots + (-1)^m.$$ Then we can take the sum on both sides, perform telescoping and in the end figure out the sum $ \sum_{k=1}^{n} k^m$. To provide a complete formula for any $m$. We need to discover another idea, but I’ll keep this for another blog.