ABSTRACT
A combinatorial proof of an identity tends to involve some kind of counting argument. Because of this, combinatorial proofs are some of the most beautiful proofs in mathematics: They frequently give more insight into why an identity is true than an argument that relies more on symbolic manipulations. Finding a good combinatorial proof is often not as straightforward as proving a result by other methods, however; while you get better at constructing combinatorial proofs with experience, it does tend to be something of an art. This chapter, in addition to proving binomial coefficient identities, is an introduction to some basic combinatorial proof techniques. We will primarily use the interpretation of ( n k ) https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351215824/80758b42-c5eb-48bc-ac2e-69d41be73879/content/eq259.tif"/> as the number of subsets of size k that can be formed from n elements, but we will also see how this way of thinking about binomial coefficients leads to other combinatorial interpretations that may not be obvious at first. For example, we will see that ( n k ) https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351215824/80758b42-c5eb-48bc-ac2e-69d41be73879/content/eq260.tif"/> counts the number of ways to choose a committee of size k from a group of n people, as well as the number of sequences of n coin flips in which exactly k flips are heads. We also discuss how binomial coefficients can be used to count certain kinds of paths in a lattice, as well as the number of selections possible when objects can be chosen more than once. In the final two sections we look at alternating sum binomial identities and two techniques for proving them: involutions and the principle of inclusion-exclusion. Finally, Chapter 8 contains several additional combinatorial proofs involving Fibonacci, Stirling, and other kinds of numbers.
