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

References

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

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