Finite Calculus, Stirling Numbers, and Cleverly Changing Basis

13 May 2021

I’m TAing a linear algebra class right now, and the other day a student came to my office hours asking about the homework. Somehow during this discussion I had a flash of inspiration that, if I ever teach a linear algebra class of my own, I would want to use as an example of changing basis “in the wild”. When I took linear algebra, all the example applications were to diagonalization and differential equations – but I”m mainly a discrete mathematician, and I would have appreciated something a bit closer to my own wheelhouse.

The observation in this post was first pointed out in a combinatorics class I took with Clinton Conley. I was aware of the theorem, but I hadn’t thought of it as a change of basis theorem until that point. I remember feeling like this was incredibly obvious, and simultaneously quite enlightening. I hope you all feel the same way about it ^_^. At the very least, this will be a nice change of pace from all the thinking I’ve been doing about power series (which should be a follow up to my post the other day) as well as a few other tricky things I’m working on. It’s nice to talk about something (comparatively) easy for a change!

---

Let’s take a second to talk about finite calculus. That wikipedia link is only so-so (at least at the time of writing), but there’s a great intro by David Gleich here and you can read more in Knuth, Graham, and Patashnik’s Concrete Mathematics (Ch 2.6) as well as the (encyclopedic) Calculus of Finite Differences by Jordan¹.

There’s a lot to say, but the tl;dr is this: Finite Calculus’s raison dêtre is to compute sums with the same facility we compute integrals (and indeed, with analogous tools). If you’ve ever been mystified by Summation by Parts², you’ve already encountered part of this machinery. I won’t go into much detail in this post, because I want to keep this short. But I highly encourage you to look into it if you spend a lot of time computing sums. Nowadays I mainly use sage, but it’s nice to know how to do some of these things by hand.

We start with discrete differentiation:

This satisfies variants of the nice rules you might want a “derivative” to satisfy:

We also get a fundamental theorem of calculus (with a much easier proof!):

---

Of course, these give us ways of combining facts we already know. In a calculus class we have a toolbox of “basic” functions that we know how to differentiate. Are there any such functions here? The answer is yes, and that leads us to the linear algebraic point of this post!

Then we have the following “power rule” for forward differences⁵:

This plus the fundamental theorem lets us quickly compute sums of “falling polynomials”. As an example:

\[\begin{align} \sum_a^b 4 x^\underline{3} - 2 x^\underline{2} + 4 &= \sum_a^b 4 x^\underline{3} - \sum_a^b 2 x^\underline{2} + \sum_a^b 4 \\ &= \sum_a^b \Delta x^\underline{4} - \frac{2}{3} \sum_a^b \Delta x^\underline{3} + 4 \sum_a^b \Delta x^\underline{1} \\ &= \left . x^\underline{4} - \frac{2}{3} x^\underline{3} + 4 x^\underline{1} \right |_a^{b+1} \\ &= \left ( (b+1)^\underline{4} - a^\underline{4} \right ) - \frac{2}{3} \left ((b+1)^\underline{3} - a^\underline{3} \right ) + 4 \left ( (b+1) - a \right ) \end{align}\]

This is great, but we don’t often see $x^{\underline{k}}$ in the wild. Most of the time we want to sum “classical” polynomials with terms like $x^k$. If only we had a way to easily convert back and forth between “classical” polynomials and “falling” polynomials…

Of course, that’s the punchline! We know the space of polynomials has a standard basis \(\{x^0, x^1, x^2, x^3, \ldots \}\). But notice the polynomials \(\{x^\underline{0}, x^\underline{1}, x^\underline{2}, x^\underline{3}, \ldots \}\) also form a basis!

And now we have a very obvious reason to care about change of basis, which I think a lot of young mathematicians would appreciate. There’s a lot of good pedagogy that one can do with this, since the new basis isn’t contrived (it comes naturally out of a desire to compute sums), and it’s an easy to understand example. Plus it’s obvious that we’re representing the same polynomial in multiple ways. In my experience a lot of students struggle with the idea that changing bases doesn’t actually change the vectors themselves, only the names we give them (i.e., their coordinates). This gives us an understandable example of that.

As a sample exercise, we might ask our students to compute $\sum_{x=1}^n x^2$. Once they know $x^2 = x^\underline{2} + x^\underline{1}$, (which can be worked out by hand without much effort) they can compute

\[\sum_1^n x^2 = \sum_1^n x^\underline{2} + x^\underline{1} = \left . \frac{x^\underline{3}}{3} + \frac{x^\underline{2}}{2} \right |_1^{n+1} = \frac{(n+1)^\underline{3} - 1^\underline{3}}{3} + \frac{(n+1)^\underline{2} - 1^\underline{2}}{2}\]

They can then check (with sage, say) that this agrees with the usual formula.

---

At this point, we’re probably sold on the idea that this alternate basis is useful for computing these sums. But it’s not yet clear how effective this is. If I ask you to compute, say, $\sum_a^b x^5$, how would you go about doing it? We need to know how to actually compute this change of basis⁶.

Enter the stirling numbers. There’s a lot of very pretty combinatorics here, but let’s focus on what’s relevant for our linear algebra. We write ${n \brace k}$ for the “stirling numbers of the second kind”, and it turns out that

\[x^n = \sum_k {n \brace k} x^\underline{k}\]

which is almost usable! All we need now is a way to quickly compute ${n \brace k}$. Thankfully, there’s jn analogue of Pascal’s Triangle that works for these coefficients!

Just like pascal’s triangle, we have $1$s down the outside, and we build the $n+1$th row by adding the two terms from the previous row which you sit between. The only difference is the stirling numbers keep track of what column you’re in as well. Concretely, the recurrence is

\[{n+1 \brace k} = {n \brace k-1} + k {n \brace k}\]

So you add the number above you and to your left to $k$ times the number above you and to your right. You increase $k$ with every step. Let’s do some sample rows together:

Say our previous row was

\[1 \quad 7 \quad 6 \quad 1\]

Then our next row will be

\[{\color{blue}1} \quad 1 + {\color{blue}2} \times 7 \quad 7 + {\color{blue}3} \times 6 \quad 6 + {\color{blue}4} \times 1 \quad 1\]

which is, of course

\[1 \quad 15 \quad 25 \quad 10 \quad 1.\]

Then the next row will be

\[{\color{blue}1} \quad 1 + {\color{blue}2} \times 15 \quad 15 + {\color{blue}3} \times 25 \quad 25 + {\color{blue}4} \times 10 \quad 10 + {\color{blue}5} \times 1 \quad 1\]

In the above example you can see the blue multiplier is just increasing by $1$ each time. We’re always combining the two entries above the current one, just like in pascal’s version.

Finally, to be super clear, if we know the $4$th row of our triangle is

\[1 \quad 7 \quad 6 \quad 1\]

that tells us that

\[x^4 = x^\underline{4} + 7 x^\underline{3} + 6 x^\underline{2} + x^\underline{1}.\]

---

Another good exercise I might give students one day is to explicitly write down change of basis matrices for, say, polynomials of degree $4$. This more or less amounts to writing the above triangle as a matrix, but hopefully it will give students something to play with to better understand how the change of basis matrices interact with the vectors.

I really think this example has staying power throughout the course as well. Once we know $\Delta$ is linear, we know it must have a representation as a matrix. Computing that representation in the falling power basis and in the standard basis would be another good exercise. One could also introduce indefinite summation (say by picking constant term $0$). Again, we know what its matrix looks like in the falling powers basis, but it’s not at all clear what it looks like in the standard basis. After conjugating by a change of basis matrix, though, we can figure this out! And the cool thing? Next time you want to compute a sum, you can just multiply by (a big enough finite part) of this matrix and evaluate at the endpoints!

If you’re a teacher and end up using this, or maybe you already were using this, definitely let me know! I’d be excited to hear about this and other ways that you try to make linear algebra feel more concrete to people learning it for the first time.

If you’re a student, hopefully this was exciting! I know I get geekier about this kind of stuff than a lot of people, but I think finite calculus is a really cool idea. Hopefully this post encourages you to go looking for other information about this technique, and maybe shows that linear algebra is never very far away ^_^.

---