Concrete Mathematics: A Foundation for Computer Science

Citation

Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley.

Chapter Summary

The book has nine chapters, followed by answers to all exercises, a bibliography, credits for exercises and an index. The preface describes the subject as a blend of continuous and discrete mathematics: the controlled manipulation of formulas, using a collection of techniques for solving problems. The emphasis is on manipulative techniques rather than on existence theorems or combinatorial reasoning. The text is informal, with student comments printed as marginal "graffiti" and quotations from earlier mathematicians.

Chapter 1: Recurrent Problems

Three problems open the book: the Tower of Hanoi, lines in the plane, and the Josephus problem. Each leads to a recurrence that is then solved.

Chapter 2: Sums

Sigma notation, the connection between sums and recurrences, the manipulation of sums, multiple sums, and general methods for evaluating them. Sections on finite and infinite calculus and on infinite sums complete the chapter.

Chapter 3: Integer Functions

Floors and ceilings and their applications, floor and ceiling recurrences, the binary "mod" operation, and sums involving floors and ceilings.

Chapter 4: Number Theory

Divisibility, primes, factorial factors, relative primality, "mod" as a congruence relation, independent residues, additional applications, and the functions φ and μ.

Chapter 5: Binomial Coefficients

The longest chapter. It starts with basic identities and practice, tricks of the trade and generating functions, then moves to hypergeometric functions and their transformations and partial hypergeometric sums. It ends with Section 5.8 on mechanical summation, the new material of the second edition, which the preface attributes to ideas of Doron Zeilberger.

Chapter 6: Special Numbers

Stirling numbers, Eulerian numbers, harmonic numbers and harmonic summation, Bernoulli numbers, Fibonacci numbers, and continuants.

Chapter 7: Generating Functions

The chapter begins with dominoes and change-making as motivating problems, then covers basic manipulations, solving recurrences, special generating functions, convolutions, exponential generating functions and Dirichlet generating functions.

Chapter 8: Discrete Probability

Definitions, mean and variance, probability generating functions, coin-flipping problems, and hashing.

Chapter 9: Asymptotics

A hierarchy of growth rates, O notation and its manipulation, two asymptotic tricks, Euler's summation formula, and a closing section of final summations.

Key Concepts

Chapters 1–3: Recurrences, Sums, Integer Functions

• Recurrence and closed form: a problem expressed through earlier values, and the aim of finding a formula without recursion.
• Finite calculus: a difference-and-sum calculus for discrete functions that parallels differentiation and integration.
• Floor and ceiling functions: integer-valued functions whose properties are developed in Chapter 3 and used throughout.

Chapters 4–6: Number Theory, Binomial Coefficients, Special Numbers

• Binomial coefficient identities: the large collection of identities of Chapter 5, with hypergeometric functions as a unifying language.
• Mechanical summation: the algorithmic approach of Section 5.8 to deciding and proving sum identities.
• Stirling, harmonic and Bernoulli numbers: sequences of special numbers that recur in sums and asymptotics.

Chapters 7–9: Generating Functions, Probability, Asymptotics

• Generating function: a power series that encodes a sequence, used to solve recurrences and count.
• Probability generating function: the same tool applied to random variables.
• O notation: the notation for bounding error terms, and the manipulation rules of Chapter 9.

Critical Analysis

Strengths

• A clear aim and an explicit method. The preface says the goal is fluency in discrete operations, comparable to a calculus student's fluency with continuous ones, and the book stays with manipulation techniques throughout.
• Exercises are central. The preface lists more than 500 exercises in six categories (warmups, basics, homework, exams, bonus and research), and the publisher notes complete answers for all except research problems, which makes the book usable for self-study. Allen Stenger's MAA Reviews notice (2010) calls it a valuable reference, loaded with useful results especially in the exercises.
• History and credit. The authors trace ideas to their sources, acknowledge the origin of exercises in an appendix, and mix quotations from Leibniz, Euler and Gauss into the margins.
• Readable style. The informal tone and student graffiti are deliberate choices described in the preface, intended to make the material easier to assimilate.

Limitations

• Narrow in scope by design. The preface notes that the topic list differs from what is usually taught in an undergraduate discrete mathematics course; logic, graph theory and proof technique are not among the chapters.
• Demanding calculation. The book expects readers to carry long manipulations by hand, and the bonus and research exercises go beyond what an average student in a course is expected to handle.
• Second-edition changes are targeted. The second edition adds Section 5.8 and corrections; the underlying text dates from the 1980s and 1990s, and the authors keep an errata list for later printings, including a correction affecting the definition of Bernoulli numbers.

Where It Fits in the Course

Concrete Mathematics is the book in this course list most devoted to computational technique. Levin's open introduction is written for students meeting mathematical reasoning for the first time; Epp's text teaches how to reason and write arguments alongside the discrete structures of computer science; Rosen's is a broad course text on logic, proof, counting and graphs; Lovász, Pelikán and Vesztergombi's short, problem-driven book starts from puzzles and simple counting. Any of these gives the background that makes Graham, Knuth and Patashnik easier.

Van Lint and Wilson's A Course in Combinatorics is a broad graduate-level text covering graph theory, designs, codes and finite geometry in many short chapters. Graham, Knuth and Patashnik complements it, since it concentrates on sums, recurrences, generating functions and asymptotics rather than on those structures.

How to Use This Book

The preface says the book grew from a Stanford course taken by juniors, seniors and mostly graduate students, and that the authors hoped to reach sophomores as well. Comfort with calculus is assumed, because calculus appears often in explanations and exercises.

• Core: Chapters 1 and 2 first, then Chapter 3 and as much of Chapters 5 and 7 as time allows. Generating functions (Chapter 7) are the most reusable tool in the book.
• Computer science emphasis: Chapters 8 and 9 for hashing, probability and the O-notation used to analyze algorithms.
• Selective: Chapter 4 can be read lightly if number theory is already familiar, and the hypergeometric sections of Chapter 5 (5.5 to 5.8) can be left for a second pass.

Try the warmup exercises of each chapter on a first reading, look at the answers only after a serious attempt, and treat the homework exercises as the real test. The preface recommends the first two habits explicitly.