## A Combinatorial Proof for the Power Sum

Probably the most common formula for the power sum $\displaystyle \sum_{k=0}^n k^m$ is the one involving binomial coefficients and Bernoulli numbers $B_k$, sometimes called Faulhaber’s formula:

$\displaystyle \sum_{k=0}^n k^m = \frac{1}{m+1} \sum_{k=0}^m \binom{m+1}{k} B_k n^{m+1-k}.$

Historically, this, or a variant of it, was the first general formula for the power sum.

There are other ways to express the power sum, though.  The subject of this post is to give a combinatorial proof for the following one involving Stirling numbers:

$\displaystyle \sum_{k=0}^n k^m = \sum_{k=1}^m \binom{n+1}{k+1} \left\{ m \atop k \right\} k! .$

Proof: How many functions f are there from the set $\{1, 2, \ldots, m+1 \}$ to the set $\{1, 2, \ldots, n+1\}$ such that $f(1) > f(j)$ for any $j \in \{2, \ldots, m+1\}$?

Answer 1: Condition on the value of $f(1)$. If $f(1) = k+1$, then there are k choices for $f(2)$, k choices for $f(3)$, etc., for a total of $k^m$ functions. Summing over all possible values of k gives the left side.

Answer 2: Condition on the number of elements in the range of f. (This is not the codomain, which is $\{1, 2, \ldots, n+1\}$, but the subset consisting of elements from the codomain that have something from $\{1, 2, \ldots, m+1\}$ mapped to them.  The range may be the entire codomain or a proper subset of it.) If the range of f has $k+1$ elements, there are $\binom{n+1}{k+1}$ ways to choose exactly which elements will comprise the range. The largest of these must be $f(1)$, and the remaining m elements in the domain must be mapped to the other k elements in the range. There are $\left\{ m \atop k \right\}$ ways to assign the remaining m elements to k nonempty groups, and then k! ways to assign these groups to the actual k remaining elements in the range. (More generally, the number of onto functions from an m-set to a k-set is $\left\{ m \atop k \right\} k!$.) Summing over all possible values of k gives the right side.

(I first gave this proof as an answer here on Math.SE.)