In this post I give combinatorial proofs of formulas for the binomial and alternating binomial power sums: and

Here’s the first.

**Identity 1.**

.

*Proof.* Both sides count the number of functions from to subsets of . For the left side, condition on the number of elements in the *codomain*. If there are *k* elements in the codomain, there are ways to choose those *k* elements from the *n* possible. Once the *k* elements in the codomain are chosen, there are *k* choices for , *k* choices for , and so forth, for a total of choices for the function values from to . 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 ways of choosing these *j* from the *n* possible. Then there are ways to complete the codomain, as any of the remaining elements in could either be in the codomain or not. In addition, there are onto functions from a set with *m* elements to a set with *j* elements. Finally, sum over all possible values of *j*.

And the second.

**Identity 2.**

.

*Proof*. We use the same interpretation as in the first proof. The left side is the difference between the number of functions from to subsets of 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 to .

Given a function , where *S* is a subset of , let *y* be the largest-numbered element of that is not in the image of *f*. Define to be the function , where such that for all but that if and if . 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 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 is defined are canceled out in the sum on the left. The only functions for which is not defined are those for which *y* does not exist. These are the onto functions from to . There are of these, and their sign is determined by whether *n* is even or odd.

For proofs of these two identities by using the formulas for and 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.

Pingback: An Alternating Convolution Identity via Sign-Reversing Involutions | A Narrow Margin