| Author | Arthur T. Benjamin, Jennifer Quinn |
|---|---|
| Genre | Mathematics |
Publication date | 2003 |
Proofs That Really Count: the Art of Combinatorial Proof is an undergraduate-level mathematics book oncombinatorial proofs ofmathematical identies. That is, it concerns equations between twointeger-valued formulas, shown to be equal either by showing that both sides of the equation count the same type of mathematical objects, or by finding aone-to-one correspondence between the different types of object that they count. It was written byArthur T. Benjamin andJennifer Quinn, and published in 2003 by theMathematical Association of America as volume 27 of their Dolciani Mathematical Expositions series. It won theBeckenbach Book Prize of the Mathematical Association of America.
The book providescombinatorial proofs of thirteen theorems in combinatorics and 246 numbered identities (collated in an appendix).[1] Several additional "uncounted identities" are also included.[2] Many proofs are based on a visual-reasoning method that the authors call "tiling",[1][3] and in a foreword, the authors describe their work as providing a follow-up for counting problems of theProof Without Words books by Roger B. Nelson.[3]
The first three chapters of the book start withinteger sequences defined by linearrecurrence relations, the prototypical example of which is the sequence ofFibonacci numbers. These numbers can be given a combinatorial interpretation as the number of ways of tiling a strip of squares with tiles of two types, single squares and dominos; this interpretation can be used to prove many of the fundamental identities involving the Fibonacci numbers, and generalized to similar relations about other sequences defined similarly,[4] such as theLucas numbers,[5] using "circular tilings and colored tilings".[6] For instance, for the Fibonacci numbers, considering whether a tiling does or does not connect positions and of a strip of length immediately leads to the identity
Chapters four through seven of the book concern identities involvingcontinued fractions,binomial coefficients,harmonic numbers,Stirling numbers, andfactorials. The eighth chapter branches out from combinatorics tonumber theory andabstract algebra, and the final chapter returns to the Fibonacci numbers with more advanced material on their identities.[4]
The book is aimed at undergraduate mathematics students, but the material is largely self-contained, and could also be read by advanced high school students.[4][6] Additionally, many of the book's chapters are themselves self-contained, allowing for arbitrary reading orders or for excerpts of this material to be used in classes.[2] Although it is structured as a textbook with exercises in each chapter,[4] reviewer Robert Beezer writes that it is "not meant as a textbook", but rather intended as a "resource" for teachers and researchers.[2] Echoing this, reviewer Joe Roberts writes that despite its elementary nature, this book should be "valuable as a reference ... for anyone working with such identities".[1]
In an initial review, Darren Glass complained that many of the results are presented as dry formulas, without any context or explanation for why they should be interesting or useful, and that this lack of context would be an obstacle for using it as the main text for a class.[4] Nevertheless, in a second review after a year of owning the book, he wrote that he was "lending it out to person after person".[7]Reviewer Peter G. Anderson praises the book's "beautiful ways of seeing old, familiar mathematics and some new mathematics too", calling it "a treasure".[5] ReviewerGerald L. Alexanderson describes the book's proofs as "ingenious, concrete and memorable".[3] The award citation for the book's 2006Beckenbach Book Prize states that it "illustrates in a magical way the pervasiveness and power of counting techniques throughout mathematics. It is one of those rare books that will appeal to the mathematical professional and seduce the neophyte."[8]
One of the open problems from the book, seeking a bijective proof of an identity combining binomial coefficients with Fibonacci numbers, was subsequently answered positively byDoron Zeilberger. In the web site where he links a preprint of his paper, Zeilberger writes,
"When I was young and handsome, I couldn't see an identity without trying to prove it bijectively. Somehow, I weaned myself of this addiction. But the urge got rekindled, when I read Arthur Benjamin and Jennifer Quinn's masterpieceProofs that Really Count."[9]
Proofs That Really Count won the 2006Beckenbach Book Prize of the Mathematical Association of America,[8] and the 2010 CHOICE Award for Outstanding Academic Title of theAmerican Library Association.[10] It has been listed by the Basic Library List Committee of the Mathematical Association of America as essential for inclusion in any undergraduate mathematics library.[4]