## The Art of Proving Binomial Identities

I recently finished a book, The Art of Proving Binomial Identities, that will be published by CRC Press later this year.  We’re past the page proofs stage, and I think all that’s left on my end is to provide a little input on the cover the CRC folks are creating.  For this post I thought I would talk a little about the background of the book, as well as what’s in it.  (UPDATE: Here’s a link to the book’s web page on the CRC site.)

Back in 2010-11 I spent a fair amount of time on what was then a new mathematics question-and-answer web site, Mathematics Stack Exchange.  The questions on Math.SE range from calculus homework problems to the occasional research-level mathematics question.  Since multiple answers are allowed for the same question, sometimes you’ll see several creative solutions for the same problem.  I became particularly intrigued by all the different ways for proving various binomial coefficient identities.  (See, for example, the answers to this question.)  However, I couldn’t find a text anywhere that pulled together all of the different methods for proving binomial identities that I was seeing on Math.SE.  So I decided to write one.  The result, many years later, is The Art of Proving Binomial Identities.

The book has ten chapters.

1. Introduction.  This chapter introduces the binomial coefficients and proves that four different definitions of the binomial coefficients are equivalent.  It also gives several proofs that the sum of row n in Pascal’s triangle is $2^n$.  The different proof techniques used give an overview of the text as a whole.
2. Basic Techniques.  This chapter is on a generalization of the binomial coefficient that allows us to prove Newton’s binomial series, binomial coefficients with negative upper indices (a special case of the just-considered generalization), the absorption identity (which has a perhaps-surprising number of applications), and binomial inversion.  The harmonic numbers make their first appearance, and we’ll see them here and there throughout the rest of the book.
3. Combinatorics.  Basic combinatorial interpretations of the binomial coefficients, such as committees and the number of successes in coin flips or ball selections, are used in this chapter to prove a variety of identities.  We also look at inclusion-exclusion, sign-reversing involutions, lattice path arguments, and choosing with replacement.  We also get our first look at the derangement numbers.
4. Calculus.  Differentiating and integrating the binomial theorem (sometimes repeatedly) can prove a lot of binomial identities.  We also look at the connection between Leibniz’s generalized product rule and the binomial theorem as well as the use of the gamma function and beta integral to prove more complicated binomial identities.
5. Probability.  The binomial, negative binomial, and hypergeometric distributions contain binomial coefficients in their probability mass functions.  Various manipulations of these pmfs, particularly moment calculations, can lead to several nice probabilistic interpretations of binomial identities.  We also introduce the technique of indicator variables in probabilistic arguments, discuss the extension of inclusion-exclusion to a probabilistic setting, and consider a probabilistic proof of the relationship between the beta integral and the binomial coefficients.
6. Generating Functions.  Generating functions are a powerful tool for proving identities.  We introduce the idea of a generating function and give several examples of their use in proving binomial identities, with particular focus on the negative binomial series, identities with central binomial coefficients, and convolution.  The last section in the chapter discusses exponential generating functions.  These are especially nice from a binomial coefficients point of view because binomial coefficients appear naturally in the sequence that is generated by the product of two egfs.
7. Recurrence Relations and Finite Differences.  This chapter introduces recurrence relations as a tool for proving binomial identities.  The bulk of the chapter, though, is devoted to exploring the relationship between binomial coefficients and finite differences.  It turns out, for instance, that the binomial coefficients arise naturally when taking repeated finite differences of the same sequence.  In addition, we discuss the relationship between the binomial transform of a sequence and the binomial transform of the finite difference of that sequence, a relationship I first explored in a paper [1] I wrote a while back.  In the last section we prove how the factorial formula for the binomial coefficients can be derived from its recurrence relation without knowing the formula in advance (a derivation which first appeared in a recent paper [2] of mine).
8. Special Numbers. The inspiration for this chapter is the chapter of the same name in the classic text Concrete Mathematics, although not all the numbers discussed are the same.  There are sections on the Fibonacci numbers, both kinds of Stirling numbers, the Bell numbers, the Lah numbers, the Catalan numbers (including more sophisticated lattice path arguments than we saw in Chapter 3), and the Bernoulli numbers.
9. Miscellaneous Techniques.  The two techniques discussed in this chapter are the use of complex numbers and linear algebra to prove binomial identities.  Substituting the imaginary unit i into the binomial theorem and separating real and imaginary parts leads to proofs of binomial identities that can be difficult to prove otherwise.  We then generalize this idea by using complex roots of unity in place of i.  For the second technique, placing Pascal’s triangle into a matrix and using matrix operations can also lead to quick proofs and new perspectives on binomial identities.  In particular, the binomial inversion technique from Chapter 2 turns out to be matrix inversion in disguise.  We also consider matrices containing Stirling, Lah, and Fibonacci numbers.
10. Mechanical Summation.  This chapter is devoted to an explanation of the automated identity proving techniques for hypergeometric sums developed by Gosper and extended by Zeilberger.  The three sections are on (1) hypergeometric series and notation, (2) Gosper’s algorithm, and (3) Zeilberger’s extension to Gosper’s algorithm.

Finally, there is an appendix containing hints and/or a solution to every problem in the text, an index of identities appearing in the text, and a general index.

References

1. Michael Z. Spivey, “Combinatorial Sums and Finite Differences,” Discrete Mathematics, 307 (24): 3130-3146, 2007.
2. Michael Z. Spivey, “The Binomial Recurrence,” Mathematics Magazine, 89 (3): 192-195, 2016.