## Concrete Mathematics: A Foundation for Computer Science, Second Edition

By Ronald L. Graham, Donald E. Knuth and Oren Patashnik

**Contents:**

1 Recurrent Problems 1

1.1 The Tower of Hanoi 1

1.2 Lines in the Plane 4

1.3 The Josephus Problem 8

Exercises 17

2 Sums 21

2.1 Notation 21

2.2 Sums and Recurrences 25

2.3 Manipulation of Sums 30

2.4 Multiple Sums 34

2.5 General Methods 41

2.6 Finite and In_nite Calculus 47

2.7 In_nite Sums 56

Exercises 62

3 Integer Functions 67

3.1 Floors and Ceilings 67

3.2 Floor/Ceiling Applications 70

3.3 Floor/Ceiling Recurrences 78

3.4 ‘mod’: The Binary Operation 81

3.5 Floor/Ceiling Sums 86

Exercises 95

4 Number Theory 102

4.1 Divisibility 102

4.2 Primes 105

4.3 Prime Examples 107

4.4 Factorial Factors 111

4.5 Relative Primality 115

4.6 ‘mod’: The Congruence Relation 123

4.7 Independent Residues 126

4.8 Additional Applications 129

4.9 Phi and Mu 133

Exercises 144

5 **Binomial Coefficients** 153

5.1 Basic Identities 153

5.2 Basic Practice 172

5.3 Tricks of the Trade 186

5.4 Generating Functions 196

5.5 Hypergeometric Functions 204

5.6 Hypergeometric Transformations 216

5.7 Partial Hypergeometric Sums 223

5.8 Mechanical Summation 229

Exercises 242

6 Special Numbers 257

6.1 Stirling Numbers 257

6.2 Eulerian Numbers 267

6.3 Harmonic Numbers 272

6.4 Harmonic Summation 279

6.5 Bernoulli Numbers 283

6.6 Fibonacci Numbers 290

6.7 Continuants 301

Exercises 309

7 Generating Functions 320

7.1 Domino Theory and Change 320

7.2 Basic Maneuvers 331

7.3 Solving Recurrences 337

7.4 Special Generating Functions 350

7.5 Convolutions 353

7.6 Exponential Generating Functions 364

7.7 Dirichlet Generating Functions 370

Exercises 371

8 Discrete Probability 381

8.1 De_nitions 381

8.2 Mean and Variance 387

8.3 Probability Generating Functions 394

8.4 Flipping Coins 401

8.5 Hashing 411

Exercises 427

9 Asymptotics 439

9.1 A Hierarchy 440

9.2 O Notation 443

9.3 O Manipulation 450

9.4 Two Asymptotic Tricks 463

9.5 Euler’s Summation Formula 469

9.6 Final Summations 476

Exercises 489

A Answers to Exercises 497

B Bibliography 604

C Credits for Exercises 632

Index 637

List of Tables 657