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 Additional Applications Phi and Mu Ch. 5 Binomial Coefficients Basic Identities Basic Practice Tricks of the Trade 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