Proofs That Really Count

Last updated

Proofs That Really Count: the Art of Combinatorial Proof is an undergraduate-level mathematics book on combinatorial proofs of 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 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.

Contents

Topics

The book provides combinatorial 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 the Proof Without Words books by Roger B. Nelson. [3]

The first three chapters of the book start with integer sequences defined by linear recurrence relations, the prototypical example of which is the sequence of Fibonacci 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 the Lucas 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 involving continued fractions, binomial coefficients, harmonic numbers, Stirling numbers, and factorials. 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. [4]

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. [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] Reviewer Gerald L. Alexanderson describes the book's proofs as "ingenious, concrete and memorable". [3] 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." [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 by Doron 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 masterpiece Proofs that Really Count." [9]

Recognition

Proofs That Really Count won the 2006 Beckenbach Book Prize of the Mathematical Association of America, [8] and the 2010 CHOICE Award for Outstanding Academic Title of the American 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]

Related Research Articles

<span class="mw-page-title-main">Bijection</span> One-to-one correspondence

A bijection, bijective function, or one-to-one correspondence between two mathematical sets is a function such that each element of the second set is mapped to from exactly one element of the first set. Equivalently, a bijection is a relation between two sets such that each element of either set is paired with exactly one element of the other set.

<span class="mw-page-title-main">Fibonacci sequence</span> Numbers obtained by adding the two previous ones

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn . The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the sequence begins

<span class="mw-page-title-main">Golden ratio</span> Number, approximately 1.618

In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities and with , is in a golden ratio to if

<span class="mw-page-title-main">Ronald Graham</span> American mathematician (1935–2020)

Ronald Lewis Graham was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He was president of both the American Mathematical Society and the Mathematical Association of America, and his honors included the Leroy P. Steele Prize for lifetime achievement and election to the National Academy of Sciences.

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

In mathematics, the Fibonacci polynomials are a polynomial sequence which can be considered as a generalization of the Fibonacci numbers. The polynomials generated in a similar way from the Lucas numbers are called Lucas polynomials.

In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof:

In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count. Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets.

Cassini's identity and Catalan's identity are mathematical identities for the Fibonacci numbers. Cassini's identity, a special case of Catalan's identity, states that for the nth Fibonacci number,

<span class="mw-page-title-main">Herbert Wilf</span> American mathematician

Herbert Saul Wilf was an American mathematician, specializing in combinatorics and graph theory. He was the Thomas A. Scott Professor of Mathematics in Combinatorial Analysis and Computing at the University of Pennsylvania. He wrote numerous books and research papers. Together with Neil Calkin he founded The Electronic Journal of Combinatorics in 1994 and was its editor-in-chief until 2001.

<span class="mw-page-title-main">Arthur T. Benjamin</span> American mathematician (born 1961)

Arthur T. Benjamin is an American mathematician who specializes in combinatorics. Since 1989 he has been a professor of mathematics at Harvey Mudd College, where he is the Smallwood Family Professor of Mathematics.

The mathematical field of combinatorics was studied to varying degrees in numerous ancient societies. Its study in Europe dates to the work of Leonardo Fibonacci in the 13th century AD, which introduced Arabian and Indian ideas to the continent. It has continued to be studied in the modern era.

<span class="mw-page-title-main">Schröder–Hipparchus number</span> Number in combinatorics

In combinatorics, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the plane trees with a given set of leaves, the ways of inserting parentheses into a sequence, and the ways of dissecting a convex polygon into smaller polygons by inserting diagonals. These numbers begin

<span class="mw-page-title-main">Jennifer Quinn</span> American mathematician

Jennifer J. Quinn is an American mathematician specializing in combinatorics, and professor of mathematics at the University of Washington Tacoma. She sits on the board of governors of the Mathematical Association of America, and is serving as its president for the years 2021 and 2022. From 2004 to 2008 she was co-editor of Math Horizons.

Gerald Lee Alexanderson (1933–2020) was an American mathematician. He was the Michael & Elizabeth Valeriote Professor of Science at Santa Clara University, and in 1997–1998 was president of the Mathematical Association of America. He was also president of The Fibonacci Association from 1980 to 1984.

The Beckenbach Book Prize, formerly known as the Mathematical Association of America Book Prize, is awarded to authors of distinguished, innovative books that have been published by the Mathematical Association of America (MAA). The prize, named in honor of Edwin F. Beckenbach, was established in 1983 and first awarded in 1985. The award is $2500 for the honored author and is awarded on an irregular basis. In January 1985 Charles Robert Hadlock was awarded the MAA Book Prize, which later in 1985 became the Beckenbach Book Prize.

Euler's Gem: The Polyhedron Formula and the Birth of Topology is a book on the formula for the Euler characteristic of convex polyhedra and its connections to the history of topology. It was written by David Richeson and published in 2008 by the Princeton University Press, with a paperback edition in 2012. It won the 2010 Euler Book Prize of the Mathematical Association of America.

Algebra and Tiling: Homomorphisms in the Service of Geometry is a mathematics textbook on the use of group theory to answer questions about tessellations and higher dimensional honeycombs, partitions of the Euclidean plane or higher-dimensional spaces into congruent tiles. It was written by Sherman K. Stein and Sándor Szabó, and published by the Mathematical Association of America as volume 25 of their Carus Mathematical Monographs series in 1994. It won the 1998 Beckenbach Book Prize, and was reprinted in paperback in 2008.

Introduction to the Theory of Error-Correcting Codes is a textbook on error-correcting codes, by Vera Pless. It was published in 1982 by John Wiley & Sons, with a second edition in 1989 and a third in 1998. The Basic Library List Committee of the Mathematical Association of America has rated the book as essential for inclusion in undergraduate mathematics libraries.

<span class="mw-page-title-main">Candido's identity</span>

Candido's identity, named after the Italian mathematician Giacomo Candido, is an identity for real numbers. It states that for two arbitrary real numbers and the following equality holds:

References

  1. 1 2 3 Roberts, Joe (2004), "Review of Proofs That Really Count", Mathematical Reviews , MR   1997773
  2. 1 2 3 Beezer, Robert A. (September 2004), "Review of Proofs That Really Count", SIAM Review , 46 (3): 562–563, JSTOR   20453541
  3. 1 2 3 Alexanderson, G. L., "Review of Proofs That Really Count", zbMATH , Zbl   1044.11001
  4. 1 2 3 4 5 6 Glass, Darren (October 2003), "Review of Proofs That Really Count", MAA Reviews, Mathematical Association of America, archived from the original on 7 December 2023
  5. 1 2 Anderson, Peter G. (November 2005), "Review of Proofs That Really Count" (PDF), Fibonacci Quarterly , 43 (4): 326–327
  6. 1 2 Rayburn, Nell (May 2004), "Review of Proofs That Really Count", The Mathematics Teacher , 97 (5): 382, JSTOR   20871635 (incorrectly credited to Larry Hoehn; see JSTOR   27971634 for authorship correction)
  7. ↑ Glass, D. (November 2004), "Review of Proofs That Really Count", The American Statistician , 58 (4): 360, doi:10.1198/tas.2004.s27, JSTOR   27643599, S2CID   118397498
  8. 1 2 "Beckenbach Prize", Prizes and Awards at the Joint Mathematics Meetings in San Antonio, Mathematical Association of America, January 18, 2006
  9. ↑ Zeilberger, Doron (2009), "A Fibonacci-counting proof begged by Benjamin and Quinn", Proceedings of the Eleventh International Conference on Fibonacci Numbers and their Applications, Congressus Numerantium, 194: 263–264, MR   2463545
  10. ↑ Proofs that Really Count: The Art of Combinatorial Proof, American Library Association, retrieved 2018-02-07
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.