Calculus, Combinatorics, and Cubes

In this level 0 post, we look at the discrete Fundamental Theorem of Calculus and see an application that brings together combinatorics and sums of cubes (and higher powers)

Introduction

For quite some time now, I have thought of mathematics as a subject that gets better as you learn it. Starting as a child, it’s all learning that there are these numbers that exist in a particular order (counting), then you learn different ways of combining numbers together (arithmetic), eventually working your way up to considering variables and the rules of algebra. It’s all rules to memorize until you get to the good stuff: proofs and theorems.

One of the main transition points in the experience of math students is calculus. In my experience, calculus was when I started to feel like I was doing math instead of merely learning it. This difference can largely be attributed to the ideas in the Fundamental Theorem of Calculus (FTC). Now, it is not necessary to know calculus in order to follow this post, basic algebra should work just fine. But the essence of the FTC is that there is basic information about how a function behaves within some interval which is encoded on the boundary of that interval. To see more precisely what I mean, here is the FTC:

$\int_a^b\,f'(x)\,dx = f(b)-f(a)$

You don’t have to understand what all the symbols mean to understand the essence. On the left-hand side, $f'(x)$ is the slope of the function $f(x)$ , and the rest of what is written amounts to considering how the slope behaves for all the values of $x$ in the region of the number line between $a$ and $b$ . On the right-hand side, you see the function evaluated just at the boundary (i.e. the end points) of the region. So information about how the function behaves within a region is encoded at the endpoints.

Discrete Calculus

There are many generalizations of the FTC to regions in the plane or on some funky surface, but recently I learned about the discrete FTC, that is the version that applies on the whole numbers. The idea is the same, but this time we will take a deeper dive into what everything means. First, we should see that a function on the whole numbers is a sequence of numbers, which we will write as $a_n$ , where $n=0,1,2,3,\ldots$ Next, we define the forward difference of a sequence to be

$\Delta a_n = a_{n+1} - a_n$ .

If you have some experience with calculus, you might recognize that this looks a lot like the definition of the derivative, but with the increment (usually called $h$ ) equal to 1. This is no coincidence. Notice also that the forward difference of a sequence is also a sequence. We will care a lot about sums of sequences, as this will form the basis of the discrete FTC. Actually, we can just prove it right now. Let’s see what the sum of the forward difference of a sequence looks like.

$\displaystyle\sum_{n=0}^{M}\Delta a_n = \Delta a_0 + \Delta a_1 + \ldots +\Delta a_M$

We can now use the definition of the forward difference to see some simplification.

$\displaystyle\sum_{n=0}^{M}\Delta a_n = (a_1-a_0) + (a_2-a_1) + \ldots+(a_{M+1}-a_M)$

Notice that there is a $+a_1$ and a $-a_1$ , which will cancel, and if we wrote down another term, we would see that there is a $-a_2$ to cancel the $+a_2$ , and this carries on all the way up until the last term. In the second-to-last term, there will be a $+a_M$ to cancel the $-a_M$ in the last term. We call this a telescoping sum because all the internal pieces cancel, and we are left with only the endpoints (sound familiar?).

$\displaystyle\sum_{n=0}^{M}\Delta a_n = a_{M+1}-a_0$

That concludes the proof! We have shown that the information about the forward difference of a sequence, for all values of $n$ between 0 and $M$ , is encoded in the original sequence at either end of the range of $n$ .

This is all well and good, but let’s get to using the discrete FTC. I have one application in mind, but we will need one more bit of information first. Let’s find the forward difference of $n^2$ .

$\Delta\left(n^2\right) = (n+1)^2 - n^2 = n^2+2n+1-n^2=2n+1$

This should be looking familiar to those who know calculus, but somethings not quite right. To make this look more like ordinary calculus, we don’t really want the extra +1 at the end. Luckily, there is a relatively easy way of getting rid of it. Enter the falling power (in this case, the falling square). It is defined to be $n^{\underline{2}}=n(n-1)$ . Let’s try the forward difference now.

$\Delta\left(n^{\underline{2}}\right) = (n+1)(n) - n(n-1) = n^2+n-n^2+n=2n^{\underline{1}}$

That looks a lot better, and more reminiscent of what you would see in a first calculus course. You might notice that instead of $n$ , I wrote the first falling power of $n.$ These are the same, but I wrote it like that to suggest the rule for the more general falling power. The falling k^th power is $n^{\underline{k}}=n(n-1)(n-2)\ldots(n-k+1)$ , and the rule for the forward difference is

$\Delta\left(n^{\underline{k}}\right) = k n^{\underline{k-1}}$ .

If you don’t believe me, try it out for a few small powers, or even try to prove it. We can combine this with the discrete FTC, and then we will be ready for our application.

$\displaystyle\sum_{n=1}^M n^{\underline{k}} = \displaystyle\sum_{n=1}^M \frac{1}{k+1}\Delta\left(n^{\underline{k+1}}\right)=\frac{(M+1)^{\underline{k+1}}}{k+1}$

For $k>0$ , the (k+1)^st falling power of 1 vanishes because you have a factor of 0, so I left it out.

Combinatorics and Cubes

There are many wonderful visual proofs, or proofs without words. Some of the more famous ones involve sums of the first $M$ numbers raised to some power $k$ , for example, the sum of the first $M$ whole numbers:

These are fun to look at and construct, but these particular proofs without words are limited by our own brains. The best we can do is go up to a sum of cubes, because you can easily draw a cube, and people will understand what you mean. Any higher powers and you are trying to draw 4-dimensional hypercubes, and no one wants to parse a visual proof like that (and certainly not a proof with 5- or 6-dimensional hypercubes!). Beyond cubes, we are forced to rely on symbols instead of pictures. But we have just developed a tool that looks a lot like summing the first $M$ numbers to the k^th power. Let’s use the discrete FTC with falling powers!

The k^th falling power is not the same thing as the k^th power, so we will have to dot some i‘s and cross some t‘s before we get our general result. Let’s see what the difference between the k^th falling power and the k^th power is.

$n^{\underline{k}}=n(n-1)\ldots(n-k+1)=n^k + c_{k-1}n^{k-1}+\ldots+c_1n^1$

This is a polynomial in $n$ , with some coefficients that I have labelled $c_i$ . Let’s see the polynomial for the first few values of $k$ .

$n^{\underline{2}}=n^2-n,\hfill n^{\underline{3}}=n^3-3n^2+2n\\ n^{\underline{4}}=n^4-6n^3+11n^2-6n$

These coefficients are useful in combinatorics. They even have a name. The coefficient of $n^{\ell}$ in the expansion of the k^th falling power of $n$ is called the $(k,\ell)$ Stirling number of the first kind, or $S_1(k,\ell)$ for short. The Stirling numbers are useful in combinatorics for counting the number of ways that you can group $k$ numbers into $\ell$ cycles. A cycle is a group of numbers which is cyclic in the sense that if you cycle the numbers in the front to the back, you consider that the same cycle. For example, $(123)$ is the same as $(231)$ or $(312)$ because to get from one to the other, you just take the number in front and put it on the end (cycling them). The cycle $(123)$ is not the same as the cycle $(213)$ because you cannot cycle numbers to get from one to the other.

In order to use our discrete FTC to do these sums, we need to express $n^k$ in terms of falling powers of $n$ . This is not too difficult for a small power, like 3. Clearly, the 3^rd falling power provides the $n^3$ term, then to get rid of any stray $n^2$ terms, you use the 2^nd falling power, and finally the 1^st falling power cleans up the $n^1$ terms (there is no constant term). In this example, we see that

$n^3 = n^{\underline{3}} + 3 n^{\underline{2}} + n^{\underline{1}}$ .

Then, we can use the discrete FTC to add up the first $M$ cubes, and we find

$\displaystyle\sum_{n=1}^M n^3 = \frac{(M+1)^{\underline{4}}}{4} + 3\frac{(M+1)^{\underline{3}}}{3} + \frac{(M+1)^{\underline{2}}}{2}\\ \displaystyle\sum_{n=1}^M n^3 = \frac{1}{4}\left(M^4+2M^3+M^2\right)$

We now have the tools to perform whichever sums we want, so long as we can find the proper way to add up the falling powers to get $n^k$ . For larger $k$ , this quickly becomes quite a daunting task. If only there was an easier way! Well, let’s look just a bit harder. I wrote a little code that generates the coefficients of the $\ell$ ^th falling powers of $n$ which together add up to $n^k$ . Here they are for the first 7 values of $k$ :

$\ell$	1	2	3	4	5	6	7
k=1	1	0	0	0	0	0	0
k=2	1	1	0	0	0	0	0
k=3	1	3	1	0	0	0	0
k=4	1	7	6	1	0	0	0
k=5	1	15	25	10	1	0	0
k=6	1	31	90	65	15	1	0
k=7	1	63	301	350	140	21	1

There are some patterns in the numbers, for sure. It looks like for $\ell=2$ , the coefficient is $2^{k-1}-1$ and for $\ell = k-1$ , the coefficient is $k(k-1)/2$ . There isn’t an obvious overall pattern, though, so I will let you in on a little secret to finding patterns in a list of integers: copy and paste them into the Online Encyclopedia of Integer Sequences (OEIS). If you paste the columns of the table into OEIS, you will find that these are the Stirling numbers of the second kind, $S_2(k,\ell)$ . When I saw this, I was more excited than I care to admit. What a nice relation to discover* between two important sets of numbers.

The Stirling numbers of the second kind are also useful in combinatorics. They count the number of ways to group $k$ objects into $\ell$ non-empty sets. We can then express $n^k$ in terms of $S_2(k,\ell)$ .

$n^k = \displaystyle\sum_{\ell=1}^{k}S_2(k,\ell)n^{\underline{\ell}}$

This finally gets us to a general formula for the sums we are after.

$\displaystyle\sum_{n=1}^M n^k = \displaystyle\sum_{\ell=1}^k \frac{(M+1)^{\underline{\ell+1}}}{\ell+1}$

Before I end, it should be noted that none of this is new. Mathematicians have known about this formula for centuries (known as Faulhaber’s formula, and typically expressed in terms of the Bernoulli numbers). Before researching this post, I wasn’t aware of Stirling numbers or Faulhaber’s formula, which I think is a good thing. The feeling of discovery, even of something which has been known to other people for centuries, is a wonderful feeling.

$\ell$	1	2	3	4	5	6	7
k=1	1	0	0	0	0	0	0
k=2	1	1	0	0	0	0	0
k=3	1	3	1	0	0	0	0
k=4	1	7	6	1	0	0	0
k=5	1	15	25	10	1	0	0
k=6	1	31	90	65	15	1	0
k=7	1	63	301	350	140	21	1

$\ell$	1	2	3	4	5	6	7
k=1	1	0	0	0	0	0	0
k=2	1	1	0	0	0	0	0
k=3	1	3	1	0	0	0	0
k=4	1	7	6	1	0	0	0
k=5	1	15	25	10	1	0	0
k=6	1	31	90	65	15	1	0
k=7	1	63	301	350	140	21	1

Introduction

Discrete Calculus

Combinatorics and Cubes

Share this:

Like this:

Related

Leave a Reply Cancel reply

$\ell$	1	2	3	4	5	6	7
k=1	1	0	0	0	0	0	0
k=2	1	1	0	0	0	0	0
k=3	1	3	1	0	0	0	0
k=4	1	7	6	1	0	0	0
k=5	1	15	25	10	1	0	0
k=6	1	31	90	65	15	1	0
k=7	1	63	301	350	140	21	1