# Contents

## 1. Recurrent Problems

1.1 The Tower of Hanoi 1.2 Lines in the Plane 1.3 The Josephus Problem Exercises

## 2. Sums

2.1 Notation 2.2 Sums and Recurrences 2.3 Manipulation of Sums 2.4 Multiple Sums 2.5 General Methods 2.6 Finite and Infinite Calculus 2.7 Infinite Sums Exercises

## 3. Integer functions

3.1 Floors and Ceilings 3.2 Floor/Ceiling Applications 3.3 Floor/Ceiling Recurrences 3.4 'mod': The Binary Operation 3.5 Floor/Ceiling Sums Exercises

## 4. Number Theory

4.1 Divisibility 4.2 Primes 4.3 Prime Examples 4.4 Factorial Factors 4.5 Relative Primality 4.6 'mod': The Congruence Relation 4.7 Independent Residues 4.8 Additional Applications 4.9 Phi and Mu Exercises

## 5. Binomial Coefficients

5.1 Basic Identities 5.2 Basic Practice 5.3 Tricks of the Trade 5.4 Generating Functions 5.5 Hypergeometric Functions 5.6 Hypergeometric Transformations 5.7 Partial Hypergeometric Sums 5.8 Mechanical Summation Exercises

## 6. Special Numbers

6.1 Stirling Numbers 6.2 Eulerian Numbers 6.3 Harmonic Numbers 6.4 Harmonic Summation 6.5 Bernoulli Numbers 6.6 Fibonacci Numbers 6.7 Continuants Exercises

## 7. Generating Functions

7.1 Domino Theory and Change 7.2 Basic Maneuvers 7.3 Solving Recurrences 7.4 Special Generating Functions 7.5 Convolutions 7.6 Exponential Generating Functions 7.7 Dirichlet Generating Functions Exercises

## 8. Discrete Probability

8.1 Definitions 8.2 Mean and Variance 8.3 Probability Generating Functions 8.4 Flipping Coins 8.5 Hashing Exercises

## 9. Asymptotics

9.1 A Hierarchy 9.2 0 Notation 9.3 0 Manipulation 9.4 Two Asymptotic Tricks 9.5 Buler's Summation Formula 9.6 Final Summations Exercises A Answers to Exercises B Bibliography C Credits for Exercises Index List of Tables