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.)

This entry was posted in binomial coefficients, combinatorics, number theory, Stirling numbers. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s