Concrete Mathematics: A Foundation for Computer Science

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
xii
CONTENTS xiii
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