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.

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 genereting-function-like trick that we already used to derive the moments of the binomial distribution!

The idea will be familiar by now. Instead of consdering 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: