# Concrete Mathematics, Second Edition

by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994), xiii+657pp.
ISBN 0-201-55802-5

Chinese translation by Lai FeiPei, Ju Ti Shu Xue (Taipei: Dong Hua Publishing Co., 1990), xv+731pp.
Chinese translation by Chen YanWen, Ju Ti Shu Xue (Taipei: Ru Lin Publishing Co., 1991), xii+695pp.
Chinese translation by Xingu Zhuang, Ju Ti Shu Xue (Xi'an: Xi An Dian Zi Ke Ji Da Xue Chu Ban She, 1992), xii+539pp.
Chinese translation by Zhang Mingyao and Zhang Fan, Ju Ti Shu Xue -- Ji Suan Ji Ke Xue Ji Chu (Beijing: Turing Books, 2013), xii+564pp.
Italian translation edited by Giovanni Monegato, Matematica Discreta (Milan: Editore Ulrico Hoepli, 1992), xviii+607pp.
Japanese translation by Makoto Arisawa, Michiaki Yasumura, Tatsuya Hagino, and Kiyoshi Ishihata, Kompyuta no Suugaku (Tokyo: Kyoritsu-Shuppan, 1993), xvi+606pp.
Portuguese translation by Valéria de Magalhães Iorio, Matemática Concreta (Rio de Janeiro: Livros Técnicos e Cientíicos Editora, 1995), xii+477pp.
Russian translation by A. B. Khodulev and B. B. Pokhodzei, with foreword by V. Arnol'd, Конкретная математика (Moscow: Mir, 1999), 703pp.; see also (Moscow: Binom, 2009).
Polish translation by P. Chrzastowski, A. Czumaj, L. Gasieniec, and M. Raczunac, Matematyka Konkretna (Warszawa: Polskie Wydawnictwa Naukowe, 1996), 718pp. (Another edition is planned for 2015.)
Hungarian translation by S. Fridli, J. Gonda, A. Kovács, L. Lakatos, and Cs. Láng, Konkrét matematika (Budapest: Műszaki Könyvkiadó, 1998), xvi+647pp.
Spanish translation (Addison-Wesley Spain and Universidad Autónoma de Madrid), in preparation.
French translation by Alain Denise, Mathématiques concrètes (Paris: International Thomson Publishing, 1998), xiv+688pp.; now distributed by Éditions Vuibert.
Croatian translation (Zagreb: Golden Marketing), in preparation.
Greek translation by Christos A. Kapoutsis (Athens: Klidarithmos), 2011), 640pp.
Macedonian translation (Skopje: Ars Lamina), in preparation.

Introduction to the mathematics that supports advanced computer programming and the analysis of algorithms. An indispensable text and reference not only for computer scientists --- the authors themselves rely heavily upon it --- but for serious users of mathematics in virtually every discipline. Based on the course Concrete Mathematics taught by Knuth at Stanford University from 1970--1989. The second edition includes important new material about the revolutionary Gosper-Zeilberger algorithm for mechanical summation. Complete answers are provided for more than 500 exercises.

It is to be hoped that this book succeeds in convincing many educators, not only in computer science but also in mathematics, that courses like this pay off! -- J. H. Van Lint, International Reviews on Education (1990)
It is always a pleasure to look again into this book full of carefully explained and enthusiastically presented mathematics. -- Volker Strehl, Mathematical Reviews (1997)
This is one of those books you keep forever, purely for its utility. -- Naomi Novik, review on amazon.com (2010)

Major topics include

• sums
• recurrences
• integer functions
• elementary number theory
• binomial coefficients
• special numbers
• generating functions
• discrete probability
• asymptotic methods

Available from the publisher, Addison-Wesley Publishing Company.

## Errata

For a list of corrections to known errors in the pre-1998 printings of the second edition, you may download the 1994--1997 errata file in compressed PostScript format (74K bytes). This file was generated by the TeX file errata97.tex in directory ftp.cs.stanford.edu:pub/concretemath.errata.old using special macros and fonts found in that directory. Errata lists for various printings of the first edition can also be found there. See also the list of errors corrected between January 1998 and May 2013, which is in HTML format.

And here is a list of all nits that have been picked so far since the 27th printing (May 2013). An asterisk (*) marks significant technical errors that are not merely typographical:

page 8, line 8
change 'only two regions per line' to 'only two regions per bent line'
page 77, line 2
change 'a real number' to 'a positive real number'
page 87, display on lines 8--10
change '$k<n$' to '$k<a^2$' under the first $\sum$; and append ', integer $a$' at the end of the formula.
pages 107 (bottom) and 108 (top)
change 'Suppose there were only finitely many ... None of the' to: 'Consider any finite set of primes, say $\{P_1,P_2,\ldots,P_k\}$. Then, said Euclid, we should think about the number
$$M=P_1\cdot P_2\cdot\ldots\cdot P_k+1.$$
None of the'
page 108, line 7 (in the 27th printing only)
change 'primes numbers' to 'prime numbers'
page 192, lines 2 and 3 from the bottom
change 'rule (5.45)' to 'rule (5.44)', and change 'way:' to 'way using (5.40):'
page 201, add new graffito in bottom half of page:
News flash: $\ln\Bscr_t(z)=\sum_{k\ge1}{tk\choose k}z^k/(tk)$; $\ln\Escr_t(z)=\sum_{k\ge1}(tk)^{k-1}z^k/k!$.
page 288, line 4
change 'sum of $n$th powers' to 'sum of $m$th powers'
page 525, new copy for answer 4.67
M. Szegedy proved this conjecture for all large n; then R. Balasubramanian and K. Soundararajan found a complete solution. See [95, pp. 78-79], [348], [55], and [19'].
page 580, replacement for lines 2 and 3 of answer 8.31
$A=1$; $B=\half zA+\half zC$; $C=\half zB+\half zD$; $D=\half zC+\half zE$; $E=\half zD+\half zA$. (And the following lines are revised to fit this better approach.)
page 580, line 3 from the bottom
change $1/x^{98}(4-2x-x^2)$ to $1/(x^{98}(4-2x-x^2))$
page 605, new reference
19' R. Balasubramanian and K. Soundararajan, “On a conjecture of R. L. Graham,” Acta Arithmetica 75 (1996), 1--38.
page 610, in reference 83
change '147--223' to '145--223'
page 638, new entry
Balasubramanian, Ramachandran, 525, 605.
page 645, Ron Graham entry
add page 605
page 653, new entry
Soundararajan, Kannan, 525, 605.

With these corrections, the authors hope that the book is now error-free. But (sigh) it probably isn't. Therefore Knuth will gratefully deposit 0x$1.00 ($2.56) to the account of the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect. Please send suggested corrections to knuth-bug@cs.stanford.edu, or send snail mail to

Prof. D. Knuth
Computer Science Department
Gates Building 4B
Stanford University
Stanford, CA 94305-9045 USA.

In either case please include your postal address, so that I can mail an official certificate of deposit as a token of thanks for any improvements to which you have contributed.

DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.

SPECIAL NOTE TO THE SPEAKERS OF FRENCH AND OTHER EXOTIC LANGUAGES: Numerous quotations and bibliographic citations found in this book have been copied verbatim from the original sources. If you believe you have found a typographic error, you must prove it by showing that the original was incorrectly transcribed; believe it or not, your language has changed over the years, just as English has.

## Sample exams

Midterm and final exams from the last two times Knuth taught this course at Stanford (1988 and 1989) are now available, together with the answers, as compressed PostScript files. The teaching assistants who helped to prepare these exams were Sheralyn Listgarten and Sridhar Raman (1988); Alan Hu and Robert Kennedy (1989).