# Summing the first $n$ powers and generating functions

One of the classic and most used sums in all of mathematics is the sum of the first $n$ natural numbers
$$1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$$ Gauss's classic derivation of this formula involves observing that if we duplicate this sum, write it backwards under the first sum, and add termwise, we get $(n+1) + (n+1) + \cdots (n+1)$, whence the original sum is half $n(n+1)$.

Similar formulas work for higher powers. For example,
$$1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}.$$ But is it a priori clear that the sum of the $a$-powers of the first $n$ natural numbers is a polynomial in $n$ with degree $a+1$? The sum of the first $n$ natural numbers is a quadratic polynomial in $n$, and the sum of the first $n$ squares is a cubic polynomial in $n$.

It is actually true that for any natural number $a$,
$$\sum_{k=0}^n k^a$$ can be written as a polynomial function of $n$ of degree $a+1$. Of course, one way to see this is to derive in a brute force manner a formula that actually works for all powers $a$. That train of thought was actually carried out by Johann Faulhaber (1580-1635) and completed by Jacobi. The resulting formula is now known as Faulhaber's formula.

Johann Faulhaber

However, that is overkill actually, if you just want to know that you can always write down a formula that is a polynomial in degree $a+1$ for $\sum^nk^a$. To prove that, you can use a generating-function-like trick that we already used to derive the moments of the binomial distribution! (Edit: to see an alternative and much shorter proof, be sure to check out Robert's comment at the bottom of this page.)

The idea will be familiar by now. Instead of considering the sum $\sum_{k=1}^n k^a$, we consider the function
$$f(t) = \sum_{k=0}^n e^{tk}.$$ Notice that I start from $k=0$ rather than $k=1$. That does not matter, except for convenience. Because now the $a$th derivative of $f$ evaluated at $t=0$ is the sum that we need. More precisely,
$$f^{(a)}(0) = \sum_{k=0}^n k^a.$$ By using the sum of a geometric series, we see that
$$f(t) = \frac{e^{t(n+1)}-1}{e^t-1}.$$ In this form, there is a point discontinuity at $t=0$ for $f(t)$ and all its derivatives. Now, the function $f^{(a)}(t)$ has in its denominator $(e^t-1)^{2a}$. We can use l'Hopital's rule to derive
$$\lim_{t\to 0} f^{(a)}.$$ By doing so, we see that after application of l'Hopital's rule, the denominator after substitution of $t=0$ will be some nonzero integer and the numerator is a polynomial in $n$.

What about the degree of this polynomial? Since
$$1^a + 2^a + \cdots +n^a \leq nn^{a} = n^{a+1},$$ we know the polynomial is at most degree $a+1$. On the other hand
$$1^a +2^a + \cdots + n^a \geq \frac{n-1}{2}\left(\frac{n-1}{2}\right)^a$$ so the polynomial is of degree at least $a+1$. Summarising:

Theorem. We have $\sum_{k=0}^n k^a = b_an^a + b_{a-1}n^{a-1} + \cdots + b_0$ for some rational numbers $b_0,\dots,b_a$.

As an aside, it might be an interesting exercise to derive some formulas for the first $n$ powers using this formula. I did try it for the sum of the first $n$ natural numbers (Gauss's sum) and already the derivation is tedious and lengthy:

• Robert says:

There's actually a much simpler proof. Consider the telescoping sum
$$\sum_{k=1}^n (k+1)^{a+1} – k^{a+1} = (n+1)^{a+1} – 1,$$
using Newton's binomium we can rewrite the term within the sum, the $k^{a+1}$ term cancels out,
$$\sum_{k=1}^n (k+1)^{a+1} – k^{a+1} = \sum_{k=1}^n ((a+1) k^a + P_{a-1}(k)),$$
where $P_{a-1}(k)$ is a polynomial in $k$ of order $a-1$. Rearranging now gives
$$\sum_{k=1}^n k^a = \frac{1}{a+1} \left( (n+1)^{a+1} – 1 – \sum_{k=1}^n P_{a-1}(k) \right),$$
and an inductive argument shows that this is a polynomial of order $a+1$. Moreover, you get that the highest power term in this polynomial is $\frac{1}{a+1}n^{a+1}$, just as you'd expect if you approximate the sum with an integral.

• Jason Polak says:

Excellent. That is indeed a much slicker and more informative proof. Thanks for writing it down here :) I will make a note in the post for readers to scroll down here so they won't miss it.