具体数学：计算机科学基础（第2版） ([美]葛立恒，[美]高德纳，[美]帕塔许尼克 张明尧，张凡)（Z-Library）

# Concrete Mathematics: A Foundation for Computer Science (2nd Edition) ## 【One-Line Pitch】 A masterclass in the mathematical techniques that underpin computer science—sums, recurrences, number theory, binomial coefficients, and generating functions—taught through concrete problems and playful exposition. Essential reading for computer science students, programmers, and anyone who wants to move beyond "abstract" math to actually solve hard quantitative problems. ## 【Book Arc】 - **Opening (~0%–9%)**: The preface and front matter establish the book's mission—a corrective to the over-abstraction of "New Math," offering a "concrete" (continuous + discrete) toolkit for real problem-solving. The authors trace the book's origins to Knuth's *Art of Computer Programming* and the Stanford course that grew from it. - **Early (~9%–32%)**: Chapter 1, "Recurrent Problems," dives straight into three classic problems—the Tower of Hanoi, lines in the plane, and the Josephus problem—to teach recurrence solving. The reader learns to name-and-solve, use small cases, and master the **repertoire method** for generalizing recurrences. - **Early (~32%–38%)**: The chapter closes with a deep exploration of the Josephus problem's binary structure, showing how changing representation (base-2, then variable bases) yields elegant closed forms. Exercises range from warm-ups to research-level challenges. - **Middle (~38%–53%)**: Chapter 2, "Sums," builds the notation and manipulation toolkit: Iverson brackets, summation factors, perturbation methods, and multiple sums. The reader learns to transform and evaluate sums with the same fluency a calculus student brings to integrals. - **Middle (~53%–end of sample)**: The chapter culminates in a showcase—eight different methods for finding the closed form of the sum of squares—demonstrating that there is rarely one "right" way, and that flexibility is the real goal. ## 【Key Takeaways】 - **Recurrences are the gateway to algorithmic thinking** (Early): The Tower of Hanoi, lines in the plane, and Josephus problem all teach the same lesson—generalize, name-and-solve, and look for patterns in small cases. This is the book's core methodology, applied throughout. - **The repertoire method is a powerful generalization tool** (Early): Instead of guessing solutions to recurrences with parameters, solve a few special cases and combine them linearly. This works best for "linear" recurrences where solutions are sums of parameter-times-function terms. - **Changing representation can unlock a problem** (Early): The Josephus recurrence becomes trivial when viewed in binary—a left cyclic shift. The book extends this to variable-base representations, showing that the right notation is often half the solution. - **Iverson brackets simplify summation enormously** (Middle): Putting a true/false proposition in brackets (yielding 1 or 0) lets you express sums with conditions directly under the Σ, making index changes and manipulations far less error-prone than with explicit bounds. - **Three laws govern all sum manipulation** (Middle): Distributivity, associativity, and commutativity (with a permutation) are the only rules you need. The perturbation method—splitting off the first and last terms—turns many sums into solvable equations. - **Multiple sums reward careful ordering** (Middle): Interchanging the order of summation is a basic move, but you must choose the order that makes the inner sum tractable. The book distinguishes "vanilla" (simple) and "rocky road" (complex) cases of this interchange. - **There is no single "right" method** (Middle): The sum of squares is solved eight different ways—from lookup tables to perturbation to calculus—each revealing a different insight. The goal is a flexible toolkit, not a recipe book. ## 【Reading Tips】 - **Work through Chapter 1 slowly and actively**: The three opening problems are deceptively simple but introduce the book's entire philosophy. Try solving each before reading the solution, and pay special attention to the repertoire method—it recurs throughout. - **Skim the front matter, but don't skip the notation section**: The "Notation" pages define nonstandard symbols (Iverson brackets, floor/ceiling, Stirling numbers) that appear constantly. Bookmark this section for reference. - **Treat exercises as part of the text**: The problem sets are graded (warm-up, homework, exam, bonus, research) and are where the real learning happens. At minimum, attempt the warm-ups and homework problems in each chapter. - **Expect to be challenged by the "research" problems**: Some exercises are genuinely open-ended. Don't get stuck—move on and return later. The authors themselves note that some are "really should be a bonus problem." - **Embrace the humor and marginalia**: The book's playful tone (jokes, asides, fake student comments) is not decoration—it signals which ideas the authors consider important or counterintuitive. The marginal notes often contain the key insight in plain language. ## 【Coverage Limits】 This guide covers the book's opening chapters (recurrences and sums) in depth. Later chapters on integer functions, number theory, binomial coefficients, special numbers, generating functions, discrete probability, and asymptotics are listed in the table of contents but not analyzed here—the sample excerpts do not extend that far. ##