Concrete mathematics: a foundation for computer science

Cover......Page 1
Concrete Mathematics (Second edition)......Page 4
Copyright......Page 5
Preface......Page 6
A Note on Notation......Page 11
Contents......Page 13
1.1 The Tower of Hanoi�����������������������������......Page 15
1.2 Lines in the Plane�����������������������������......Page 18
1.3 The Josephus Problem�������������������������������......Page 22
Exercises����������������......Page 31
2.1 Notation�������������������......Page 35
2.2 Sums and Recurrences�������������������������������......Page 39
2.3 Manipulation of Sums�������������������������������......Page 44
2.4 Multiple Sums������������������������......Page 48
2.5 General Methods��������������������������......Page 55
2.6 Finite and Infinite Calculus���������������������������������������......Page 61
2.7 Infinite Sums������������������������......Page 70
Exercises����������������......Page 76
3.1 Floors and Ceilings������������������������������......Page 81
3.2 Floor/Ceiling Applications�������������������������������������......Page 84
3.3 Floor/Ceiling Recurrences������������������������������������......Page 92
3.4 \'mod\': The Binary Operation��������������������������������������......Page 95
3.5 Floor/Ceiling Sums�����������������������������......Page 100
Exercises����������������......Page 109
4.1 Divisibility�����������������������......Page 116
4.2 Primes�����������������......Page 119
4.3 Prime Examples�������������������������......Page 121
4.4 Factorial Factors����������������������������......Page 125
4.5 Relative Primality�����������������������������......Page 129
4.6 \'mod\': The Congruence Relation�����������������������������������������......Page 137
4.7 Independent Residues�������������������������������......Page 140
4.8 Additional Applications����������������������������������......Page 143
4.9 Phi and Mu���������������������......Page 147
Exercises����������������......Page 158
5.1 Basic Identities���������������������������......Page 167
5.2 Basic Practice�������������������������......Page 186
5.3 Tricks of the Trade������������������������������......Page 200
5.4 Generating Functions�������������������������������......Page 210
5.5 Hypergeometric Functions�����������������������������������......Page 218
5.6 Hypergeometric Transformations�����������������������������������������......Page 230
5.7 Partial Hypergeometric Sums��������������������������������������......Page 237
5.8 Mechanical Summation�������������������������������......Page 243
Exercises����������������......Page 256
6.1 Stirling Numbers���������������������������......Page 271
6.2 Eulerian Numbers���������������������������......Page 281
6.3 Harmonic Numbers���������������������������......Page 286
6.4 Harmonic Summation�����������������������������......Page 293
6.5 Bernoulli Numbers����������������������������......Page 297
6.6 Fibonacci Numbers����������������������������......Page 304
6.7 Continuants����������������������......Page 315
Exercises����������������......Page 323
7.1 Domino Theory and Change�����������������������������������......Page 334
7.2 Basic Maneuvers��������������������������......Page 345
7.3 Solving Recurrences������������������������������......Page 351
7.4 Special Generating Functions���������������������������������������......Page 364
7.5 Convolutions�����������������������......Page 367
7.6 Exponential Generating Functions�������������������������������������������......Page 378
7.7 Dirichlet Generating Functions�����������������������������������������......Page 384
Exercises����������������......Page 385
8.1 Definitions����������������������......Page 395
8.2 Mean and Variance����������������������������......Page 401
8.3 Probability Generating Functions�������������������������������������������......Page 408
8.4 Flipping Coins�������������������������......Page 415
8.5 Hashing������������������......Page 425
Exercises����������������......Page 441
9 Asymptotics��������������������......Page 453
9.1 A Hierarchy����������������������......Page 454
9.2 O Notation���������������������......Page 457
9.3 O Manipulation�������������������������......Page 464
9.4 Two Asymptotic Tricks��������������������������������......Page 477
9.5 Euler\'s Summation Formula������������������������������������......Page 483
9.6 Final Summations���������������������������......Page 490
Exercises����������������......Page 503
A. Answers to Exercises......Page 511
B. Bibliography......Page 618
C. Credits for Exercises......Page 646
Index������������......Page 651
List of Tables���������������������......Page 671
Errata, 1994–1997......Page 673