You are here

Concrete Mathematics: A Foundation for Computer Science

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik
Publisher: 
Addison-Wesley
Publication Date: 
1994
Number of Pages: 
672
Format: 
Hardcover
Edition: 
2
Price: 
64.99
ISBN: 
9780201558029
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee considers this book essential for undergraduate mathematics libraries.

[Reviewed by
Allen Stenger
, on
11/18/2010
]

This book is subtitled “A Foundation for Computer Science”, and this is an accurate description, but it is equally accurate to say that it is a foundation for discrete math. The great strength of this book is that it teaches you how to attack problems in this area systematically, without depending on luck, inspiration, or finding the right formula (although these still help). The prerequisites for the book are fairly low; it assumes that you are somewhat familiar with discrete math, but does not require deep knowledge.

The intriguing title “concrete math” is explained as being in contrast to abstract math, and a little less plausibly as a portmanteau of CONtinuous and disCRETE math. In fact the subject matter is much closer to discrete math, but unlike typical discrete math texts it assumes you have already analyzed the problem and you have now some unwieldy formula or recursion that needs to be put into a more useful form. This may sound very specialized, but in fact a large part of the work in discrete math problems is of this nature. The book originated as a course at Stanford based on the first 100 pages of Knuth’s The Art of Computer Programming, Volume 1: Fundamental Algorithms and is slanted somewhat toward math needed for the analysis of algorithms.

The book is especially strong on “special numbers” such as the binomial coefficients and the Bernoulli numbers; these play the role in discrete math that special functions play in classical analysis. There is also a very good chapter on the technique of generating functions, there are methods of solving recurrences and evaluating finite sums scattered through the book, and there’s quite a lot on hypergeometric series. Nearly all of the book deals strictly with discrete problems, and concentrates on manipulations to bring them into a usable form. This doesn’t always work, so the last chapter deals with asymptotic analysis to transform these difficult cases into useful approximations.

The book includes a thorough discussion of the Gosper and the WZ (Wilf–Zeilberger) methods for evaluating finite sums and proving identities involving finite sums. This is titled “mechanical summation”, and indeed it is so cumbersome that it should be left to computers, but anyone working with finite sums should be aware that it exists and should check if it applies to his sum.

Although designed as a textbook, the book is also a valuable reference, and is loaded with useful results, especially in the exercises (all of which are solved in the back of the book). This is my go-to book for any problem dealing with binomial coefficients, Fibonacci numbers, harmonic numbers, or evaluation of finite sums.


Allen Stenger is a math hobbyist and retired software developer. He is webmaster and newsletter editor for the MAA Southwestern Section and is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis. He volunteers in his spare time at MathNerds.org, a math help site that fosters inquiry learning.


 

1. Recurrent Problems.

 

The Tower of Hanoi.

 

 

Lines in the Plane.

 

 

The Josephus Problem.

 

 

Exercises.

 



2. Sums.

 

Notation.

 

 

Sums and Recurrences.

 

 

Manipulation of Sums.

 

 

Multiple Sums.

 

 

General Methods.

 

 

Finite and Infinite Calculus.

 

 

Infinite Sums.

 

 

Exercises.

 



3. Integer Functions.

 

Floors and Ceilings.

 

 

Floor/Ceiling Applications.

 

 

Floor/Ceiling Recurrences.

 

 

'mod': The Binary Operation.

 

 

Floor/Ceiling Sums.

 

 

Exercises.

 



4. Number Theory.

 

Divisibility.

 

 

Factorial Factors.

 

 

Relative Primality.

 

 

'mod': The Congruence Relation.

 

 

Independent Residues.

 

 

Additional Applications.

 

 

Phi and Mu.

 

 

Exercises.

 



5. Binomial Coefficients.

 

Basic Identities.

 

 

Basic Practice.

 

 

Tricks of the Trade.

 

 

Generating Functions.

 

 

Hypergeometric Functions.

 

 

Hypergeometric Transformations.

 

 

Partial Hypergeometric Sums.

 

 

Mechanical Summation.

 

 

Exercises.

 



6. Special Numbers.

 

Stirling Numbers.

 

 

Eulerian Numbers.

 

 

Harmonic Numbers.

 

 

Harmonic Summation.

 

 

Bernoulli Numbers.

 

 

Fibonacci Numbers.

 

 

Continuants.

 

 

Exercises.

 



7. Generating Functions.

 

Domino Theory and Change.

 

 

Basic Maneuvers.

 

 

Solving Recurrences.

 

 

Special Generating Functions.

 

 

Convolutions.

 

 

Exponential Generating Functions.

 

 

Dirichlet Generating Functions.

 

 

Exercises.

 



8. Discrete Probability.

 

Definitions.

 

 

Mean and Variance.

 

 

Probability Generating Functions.

 

 

Flipping Coins.

 

 

Hashing.

 

 

Exercises.

 



9. Asymptotics.

 

A Hierarchy.

 

 

O Notation.

 

 

O Manipulation.

 

 

Two Asymptotic Tricks.

 

 

Euler's Summation Formula.

 

 

Final Summations.

 

 

Exercises.

 



A. Answers to Exercises.


B. Bibliography.


C. Credits for Exercises.


Index.