Combinatorial Proofs for the Binomial and Alternating Binomial Power Sums

In this post I give combinatorial proofs of formulas for the binomial and alternating binomial power sums: \displaystyle \sum_{k=0}^n \binom{n}{k} k^m and \displaystyle \sum_{k=0}^n \binom{n}{k} k^m (-1)^k.

Here’s the first.

Identity 1.

\displaystyle \sum_{k=0}^n \binom{n}{k} k^m = \sum_{j=0}^m \left\{ {m \atop j} \right\} \binom{n}{j} j! 2^{n-j}.

Proof.  Both sides count the number of functions from \{1, 2, \ldots, m\} to subsets of \{1, 2, \ldots, n\}.  For the left side, condition on the number of elements in the codomain.   If there are k elements in the codomain, there are \binom{n}{k} ways to choose those k elements from the n possible.  Once the k elements in the codomain are chosen, there are k choices for f(1)k choices for f(2), and so forth, for a total of k^m choices for the function values from f(1) to f(m).  Summing over all possible values of k gives the left side.

For the right side, condition on the number of elements in the image.  If there are j elements in the image, there are \binom{n}{j} ways of choosing these j from the n possible.  Then there are 2^{n-j} ways to complete the codomain, as any of the remaining n-j elements in \{1, 2, \ldots, n\} could either be in the codomain or not.  In addition, there are \left\{ {m \atop j } \right\} j! onto functions from a set with m elements to a set with j elements.  Finally, sum over all possible values of j.    \square

And the second.

Identity 2.

\displaystyle \sum_{k=0}^n \binom{n}{k} k^m (-1)^k = (-1)^n \left\{ m \atop n \right\} n!.

Proof.  We use the same interpretation as in the first proof.  The left side is the difference between the number of functions from \{1, 2, \ldots, m\} to subsets of \{1, 2, \ldots, n\} with an even-sized codomain and the number of such functions with an odd-sized codomain.  We construct a sign-reversing involution on the set of functions from \{1, 2, \ldots, m\} to \{1, 2, \ldots n\}.

Given a function f: \{1, 2, \ldots, m\} \mapsto S, where S is a subset of \{1, 2, \ldots, n\}, let y be the largest-numbered element of \{1, 2, \ldots, n\} that is not in the image of f.  Define \sigma(f) to be the function g: \{1, 2, \ldots, m\} \mapsto T, where T \subseteq \{1, 2, \ldots, n\} such that f(x) = g(x) for all x \in \{1, 2, \ldots, m\} but that T = S \cup \{y\} if y \not\in S and T = S - \{y\} if y \in S.  In other words, f and g are the same function except that the codomain of exactly one of them contains the largest-numbered element not in their common image.  From this definition we can see that \sigma is both sign-reversing (as it maps functions with even-sized codomains to those with odd-sized codomains and vice versa) and an involution.  Thus the functions for which \sigma is defined are canceled out in the sum on the left.  The only functions for which \sigma is not defined are those for which y does not exist.  These are the onto functions from \{1, 2, \ldots, m\} to \{1, 2, \ldots, n\}.  There are \left\{ {m \atop n } \right\} n! of these, and their sign is determined by whether n is even or odd.  \square

For proofs of these two identities by using the formulas for \displaystyle \sum_{k=0}^n \binom{n}{k} k^{\underline{m}} and \displaystyle \sum_{k=0}^n \binom{n}{k} k^{\underline{m}} (-1)^k and then using the Stirling numbers of the second kind to convert from falling factorial powers to ordinary powers, see my paper [1].

References

[1]  Michael Z. Spivey.  “Combinatorial Sums and Finite Differences.”  Discrete Mathematics 307 (24): 3130-3146, 2007.

Advertisements
This entry was posted in binomial coefficients, combinatorics, 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