```Notes on Concrete Mathematics by Knuth, Graham, and Patashnik

Contents

Ch. 1 Recurrent Problems
The Tower of Hanoi
Lines in the Plane
The Josephus Problem

Ch. 2 Sums
Notation
Sums and Recurrences
Manipulation of Sums
Multiple Sums
General Methods
Finite and Infinite Calculus
Infinite Sums

Ch. 3 Integer Functions
Floors and Ceilings
Floor/Ceiling Applications
Floor/Ceiling Recurrences
'mod': The Binary Operation
Floor/Ceiling Sums

Ch. 4 Number Theory
Divisibility
Primes
Prime Examples
Factorial Factors
Relative Primality
'mod': The congruence Relation
Independent Residues
Phi and Mu

Ch. 5 Binomial Coefficients
Basic Identities
Basic Practice
Generating Functions
Hypergeometric Functions
Hypergeometric Transformations
Partial Hypergeometric Sums
Mechanical Summation

Ch. 6 Special Numbers
Stirling Numbers
Eulerian Numbers
Harmonic Numbers
Harmonic Summation
Bernoulli Numbers
Fibonacci Numbers
Continuants

Ch. 7 Generating Functions
Domino Theory and Change
Basic Maneuvers
Solving Recurrences
Special Generating Functions
Convolutions
Exponential Generating Functions
Dirichlet Generating Functions

Ch. 8 Discrete Probability
Definitions
Mean and Variance
Probability Generating Functions
Flipping Coins
Hashing

Ch. 9 Asymptotics
A Hierarchy
O Notation
O Manipulation
Two Asymptotic Tricks
Euler's Summation Formula
Final Summations

Recurrent Problems

The Tower of Hanoi
Assume
8 disks 'stacked in decreasing size on one of three pegs'
move 'one disk at a time'
never move 'one onto a smaller one'
it is possible to 'transfer the entire tower to one of the other pegs'
'What is the best we can do?'
'How many moves are necessary and sufficient to perform the task?'
Assume there are n disks (generalize the problem)
'Look at small cases first'
'Name and conquer'
Define T n as the minimum number of moves that transfer n disks between pegs
Assume the following method transfers n disks
transfer the n - 1 smallest to a different peg (T n - 1 moves)
move the largest (1 move)
transfer the n - 1 smallest onto the largest (T n - 1 moves)
Thus (1 < n) implies (T n) <: 1 + 2 * T n - 1
Note, to move largest disk, n - 1 smaller disks must be on a peg so >: T n -
1 moves
Note, largest disk is moved at least once
Note, n - 1 smaller disks must be moved on largest disk so >: T n - 1 moves
Thus (1 < n) implies (T n) >: 1 + 2 * T n - 1
Thus T satisfies the recurrence
(T 0) = 0
(T n) = 1 + 2 * T n - 1 for n > 0
Note (T 0) = (2 ^ 0) - 1
Assume (T n - 1) = (2 ^ n - 1) - 1 then
T n
1 + 2 * T n - 1
1 + 2 * (2 ^ n - 1) - 1
1 + (2 ^ n) - 2
(2 ^ n) - 1
Thus, by induction, (T n) = (2 ^ n) - 1
Note, when 'finding a closed form expression for some quantity of interest'
'Look at small cases.'
'Find and prove a mathematical expression for the quantity.'
'Find and prove a closed form for a mathematical expression'

Lines in the Plane
Define L n as the maximum number of regions defined by n lines in the plane
Note 0 < n implies nth line adds k regions iff it hits lines at k - 1
different points
Assume two lines intersect in at most one point
Thus nth line intersects n - 1 lines at less than n - 1 points
Thus (0 < n) implies (L n) <: n + L n - 1
```