Several years ago I attended a conference at which Arthur Benjamin, one of the authors of the book under review, gave a talk about Fibonacci Numbers. In particular, he gave the following interpretation. Let fn count the number of ways to tile an n-by-1 board with 1-by-1 square tiles and 2-by-1 domino tiles. One can show that fn = Fn+1, where Fn is the standard nth Fibonacci number defined by F0 = 0, F1 = 1, and the recursion relation Fn = Fn-1 + Fn-2. He proceeded to show how this definition could be used to give a combinatorial proof of many of the Fibonacci Number identities that we are familiar with, such as Fm+n=Fm+1Fn + FmFn-1.
The talk concluded with Benjamin giving a sketch of how this definition of Fibonacci Numbers, along with a little bit of probability theory, could be used to prove Binet's closed formula for Fn. That evening I was flying across the country back home, and due to a bit of unfortunate weather I was forced to spend the night in the St Louis airport. This was in many ways a miserable experience, but I pulled out a legal pad and started trying to use the tantalizing bits of what Benjamin had said in his talk to (re-)create the promised proof of Binet's Formula. It was the perfect problem for this kind of situation: one that I could easily keep in my head, one that I knew the right answer to, and one that had a couple of really clever ideas to ponder.
Proofs That Really Count: The Art of Combinatorial Proof, the new book co-written by Benjamin and Jennifer Quinn, is full of exactly this kind of problem and solution. There are two types of examples in the book: in the first kind they count the elements of a set in two different ways, and then obtain an identity by setting the answers equal. In the second kind they construct two different sets and a bijection (or a near-bijection) between them in order to prove an identity by setting the sizes to be equal (or nearly equal). With essentially only those two techniques, they prove many results in combinatorics and number theory. The writing in the book is very sharp and I found the book to be thoroughly engaging.
Chapter One of the book sets up the approach that the entire book will take, and focuses on the Fibonacci examples. Chapter Two generalizes this by looking at the so-called Gibonacci numbers (which are defined by the same recursion relation but arbitrary G0 and G1) and Lucas numbers (the special case where L0 = 2, L1 = 1 and Ln = Ln-1+Ln-2). Chapter Three generalizes even further by looking at sequences defined by any linear recurrence, and giving combinatorial approaches to thinking about these and proving various relationships. Chapter Four was the one I found the most interesting, as it gives an entirely new (to me) combinatorial approach to thinking about continued fractions. The next two chapters look at binomial coefficients, which have obvious combinatorial interpretations that the authors exploit to prove many identities. Chapter Seven looks at Harmonic Numbers, the partial sums of the Harmonic series, as well as Stirling Numbers. This chapter contains a discussion of permutation groups that any abstract algebra student would benefit from reading. Chapter Eight discusses some identities in number theory and algebra. The book concludes with one final chapter on "Advanced Fibonacci and Lucas Identites", in which the authors give a much slicker version of the proof of Binet's formula than I was able to come up with in the food court of the Saint Louis airport, as well as other identities. Every chapter comes with a collection of exercises or open problems, and the authors provide hints to many of these exercises. Furthermore, all of the identities that are proven in the text are collected in an appendix, making this book an excellent reference book.
The authors have succeeded in writing a book that will be accessible to a very broad audience. Much of the book literally consists of reducing complicated identities to counting, and therefore is accessible to undergraduates and even to motivated high school students. On the other hand, while the theorems covered may not be new to research mathematicians, I would wager that very few of us have seen them proven in quite this way. The illustrations in the book deserve special note, for they are not only used extremely well, but the authors are able to use black and white to denote many different colors in a way that truly works.
My only complaint with the book is that it lacks context for many of the results. While seeing one or two Fibonacci identities proved in a new way is interesting to me, after reading fifteen pages of identity after identity they all seemed to blur together, and it was unclear to me why I should care that, say,
Gn = G0Fn-2 + G1Fn-1.
While many combinatorialists may find it clear why this type of fact is interesting — or believe that it is interesting merely for the fact that it is true — the fact that this is not clear to me makes me think that it would be even less clear to a student. This is even truer in the chapter on number theory, where I would have liked to see some description of why, for example, Fermat's Little Theorem is an important and useful result alongside the clever combinatorial proof that the author gives.
This complaint might stop me from using Proofs That Really Count as the sole textbook for a course or giving it to a student to read without any context. But with exposition this engaging, and problems as well as topics that stick in your brain in the way that these do, there is certainly much in this book to recommend. Anyone teaching a course in combinatorics should have a copy of this book nearby to come up with interesting problems or readings to give the students, as Benjamin and Quinn succeed in most of the ways that really count.
Darren Glass is a VIGRE Assistant Professor of Mathematics at Columbia University. His research interests include number theory, algebraic geometry, and cryptography. He can be reached at (firstname.lastname@example.org).