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
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 Infinite Calculus 47
2.7 Infinite Sums 56
Exercises 62
21
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
Exercises 230
6 Special Numbers 243
6.1 Stirling Numbers 243
6.2 Eulerian Numbers 253
6.3 Harmonic Numbers 258
6.4 Harmonic Summation 265
6.5 Bernoulli Numbers 269
6.6 Fibonacci Numbers 276
6.7 Continuants 287
Exercises 295
7 Generating Functions 306
7.1 Domino Theory and Change 306
7.2 Basic Maneuvers 317
7.3 Solving Recurrences 323
7.4 Special Generating Functions 336
7.5 Convolutions 339
7.6 Exponential Generating Functions 350
7.7 Dirichlet Generating Functions 356
Exercises 357
8 Discrete Probability 367
8.1 Definitions 367
8.2 Mean and Variance 373
8.3 Probability Generating Functions 380
8.4 Flipping Coins 387
8.5 Hashing 397
Exercises 413
9 Asymptotics 425
9.1 A Hierarchy 426
9.2 0 Notation 429
9.3 0 Manipulation 436
9.4 Two Asymptotic Tricks 449
9.5 Euler’s Summation Formula 455
9.6 Final Summations 462
Exercises 475
A Answers to Exercises 483
B Bibliography 578
C Credits for Exercises 601
Index 606
List of Tables 624
Other Mathematics Books
Download
No comments:
Post a Comment