View source for Proofs That Really Count

{{short description|2003 mathematics book by Arthur T. Benjamin and Jennifer Quinn}}{{Infobox book
| author            = Arthur T. Benjamin, Jennifer Quinn
| pub_date          = 2003
| name              = Proofs That Really Count: the Art of Combinatorial Proof
| genre             = Mathematics
}}

{{italic title}}
'''''Proofs That Really Count: the Art of Combinatorial Proof''''' is an undergraduate-level mathematics book on [[combinatorial proof]]s of [[Identity (mathematics)|mathematical identies]]. That is, it concerns equations between two [[integer]]-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 a [[bijective proof|one-to-one correspondence]] between the different types of object that they count. It was written by [[Arthur T. Benjamin]] and [[Jennifer Quinn]], and published in 2003 by the [[Mathematical Association of America]] as volume 27 of their Dolciani Mathematical Expositions series. It won the [[Beckenbach Book Prize]] of the Mathematical Association of America.

==Topics==
The book provides [[combinatorial proof]]s of thirteen theorems in combinatorics and 246 numbered identities (collated in an appendix).{{r|roberts}} Several additional "uncounted identities" are also included.{{r|beezer}} Many proofs are based on a visual-reasoning method that the authors call "tiling",{{r|roberts|alexanderson}} and in a foreword, the authors describe their work as providing a follow-up for counting problems of the ''Proof Without Words'' books by Roger B. Nelson.{{r|alexanderson}}

The first three chapters of the book start with [[integer sequence]]s defined by linear [[recurrence relation]]s, the prototypical example of which is the sequence of [[Fibonacci number]]s. These numbers can be given a combinatorial interpretation as the number of ways of tiling a <math>1\times n</math> 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,{{r|glass}} such as the [[Lucas number]]s,{{r|anderson}} using "circular tilings and colored tilings".{{r|rayburn}} For instance, for the Fibonacci numbers, considering whether a tiling does or does not connect positions <math>a-1</math> and <math>a</math> of a strip of length <math>a+b-1</math> immediately leads to the identity
:<math>F_{a+b}=F_{a-1}F_{b}+F_aF_{b+1}.</math>

Chapters four through seven of the book concern identities involving [[continued fraction]]s, [[binomial coefficient]]s, [[harmonic number]]s, [[Stirling number]]s, and [[factorial]]s. The eighth chapter branches out from combinatorics to [[number theory]] and [[abstract algebra]], and the final chapter returns to the Fibonacci numbers with more advanced material on their identities.{{r|glass}}

==Audience and reception==
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.{{r|glass|rayburn}} 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.{{r|beezer}} Although it is structured as a textbook with exercises in each chapter,{{r|glass}} reviewer Robert Beezer writes that it is "not meant as a textbook", but rather intended as a "resource" for teachers and researchers.{{r|beezer}} 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".{{r|roberts}}

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.{{r|glass}} Nevertheless, in a second review after a year of owning the book, he wrote that he was "lending it out to person after person".{{r|glass2}}
Reviewer Peter G. Anderson praises the book's "beautiful ways of seeing old, familiar mathematics and some new mathematics too", calling it "a treasure".{{r|anderson}} Reviewer [[Gerald L. Alexanderson]] describes the book's proofs as "ingenious, concrete and memorable".{{r|alexanderson}} The award citation for the book's 2006 [[Beckenbach 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."{{r|beckenbach}}

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 by [[Doron Zeilberger]]. In the web site where he links a preprint of his paper, Zeilberger writes,
{{quote|"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 masterpiece ''Proofs that Really Count''."{{r|zeilberger}}}}

==Recognition==
''Proofs That Really Count'' won the 2006 [[Beckenbach Book Prize]] of the Mathematical Association of America,{{r|beckenbach}} and the 2010 CHOICE Award for Outstanding Academic Title of the [[American Library Association]].{{r|ala}} 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.{{r|glass}}

==References==
{{reflist|refs=

<ref name=ala>{{citation|url=http://www.ala.org/awardsgrants/content/proofs-really-count-art-combinatorial-proof-0|title=Proofs that Really Count: The Art of Combinatorial Proof|publisher=American Library Association|accessdate=2018-02-07}}</ref>

<ref name=alexanderson>{{citation
 | last = Alexanderson | first = G. L. | author-link = Gerald L. Alexanderson
 | journal = [[zbMATH]]
 | title = Review of ''Proofs That Really Count''
 | zbl = 1044.11001}}</ref>

<ref name=anderson>{{citation
 | last = Anderson | first = Peter G.
 | date = November 2005
 | issue = 4
 | journal = [[Fibonacci Quarterly]]
 | pages = 326–327
 | title = Review of ''Proofs That Really Count''
 | url = https://www.fq.math.ca/Papers1/43-4/paper43-4-6.pdf
 | volume = 43| doi = 10.1080/00150517.2005.12428352
 }}</ref>

<ref name=beckenbach>{{citation|url=https://www.maa.org/news/prizes-and-awards-at-the-joint-mathematics-meetings-in-san-antonio|title=Beckenbach Prize|work=Prizes and Awards at the Joint Mathematics Meetings in San Antonio|publisher=Mathematical Association of America|date=January 18, 2006}}</ref>

<ref name=beezer>{{citation
 | last = Beezer | first = Robert A.
 | date = September 2004
 | issue = 3
 | journal = [[SIAM Review]]
 | jstor = 20453541
 | pages = 562–563
 | title = Review of ''Proofs That Really Count''
 | volume = 46}}</ref>

<ref name=glass>{{citation
 | last = Glass | first = Darren
 | date = October 2003
 | journal = MAA Reviews
 | publisher = [[Mathematical Association of America]]
 | title = Review of ''Proofs That Really Count''
 | url = https://www.maa.org/press/maa-reviews/proofs-that-really-count
 | archive-url = https://web.archive.org/web/20231207204240/https://maa.org/press/maa-reviews/proofs-that-really-count
 | archive-date = 7 December 2023
 | url-status = dead}}</ref>

<ref name=glass2>{{citation
 | last = Glass | first = D.
 | date = November 2004
 | issue = 4
 | journal = [[The American Statistician]]
 | jstor = 27643599
 | page = 360
 | title = Review of ''Proofs That Really Count''
 | volume = 58| doi = 10.1198/tas.2004.s27
 | s2cid = 118397498
 }}</ref>

<ref name=rayburn>{{citation
 | last = Rayburn | first = Nell
 | date = May 2004
 | issue = 5
 | journal = [[The Mathematics Teacher]]
 | jstor = 20871635
 | page = 382
 | title = Review of ''Proofs That Really Count''
 | volume = 97}} (incorrectly credited to Larry Hoehn; see {{JSTOR|27971634}} for authorship correction)</ref>

<ref name=roberts>{{citation
 | last = Roberts | first = Joe
 | journal = [[Mathematical Reviews]]
 | mr = 1997773
 | title = Review of ''Proofs That Really Count''
 | year = 2004}}</ref>

<ref name=zeilberger>{{citation
 | last = Zeilberger | first = Doron | authorlink = Doron Zeilberger
 | department = Proceedings of the Eleventh International Conference on Fibonacci Numbers and their Applications
 | journal = Congressus Numerantium
 | mr = 2463545
 | pages = 263–264
 | title = A Fibonacci-counting proof begged by Benjamin and Quinn
 | url = https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/fib.html
 | volume = 194
 | year = 2009}}</ref>

}}

==External links==
*[https://archive.org/details/proofsthatreally0000benj ''Proofs That Really Count''] on the [[Internet Archive]]

[[Category:Enumerative combinatorics]]
[[Category:Mathematical proofs]]
[[Category:Mathematics books]]
[[Category:2003 non-fiction books]]