Analysis of Algorithms (Coursera)
by Robert Sedgewick · Princeton University / Coursera
Princeton course by Robert Sedgewick, free to audit, based on the Sedgewick-Flajolet textbook. Lectures cover recurrence relations, generating functions, and asymptotics applied to sorting, trees, and strings. Chapter 2 notes are on the aofa.cs.princeton.edu booksite. Shows recurrences doing real work in algorithm analysis, from first-order recurrences to generating-function solutions.
More resources on Recurrence Relations
Wolfram MathWorld
MathWorld is an online mathematics encyclopedia from Wolfram Research offering detailed, browsable articles on topics across the math spectrum, including algebra, geometry, calculus, and number theory. Each entry includes definitions, theorems, formulas, diagrams, worked examples, and links to further reading.
Art of Problem Solving
Art of Problem Solving wiki article defining recurrence relations and showing how to solve linear recurrences with constant coefficients through the characteristic polynomial, using examples such as the Fibonacci sequence. Prepares readers to find closed forms for recurrences that arise in competition counting problems.
Mathematics for Computer Science (MIT 6.042J)
Discrete mathematics for computer science with an emphasis on definitions and proofs: logic, induction, sets and relations, graph theory, modular arithmetic, asymptotics, counting and discrete probability. 25 lecture videos, problem sets and exams with solutions build fluency in writing proofs.
generatingfunctionology
Wilf's text on generating functions, with the second edition free to download from his Penn page. Chapter 1 converts recurrences into generating functions and solves them, then the book covers formal power series, counting, and asymptotic estimates. Standard next step after characteristic roots: solving recurrences with generating functions.
Concrete Mathematics: A Foundation for Computer Science (2nd Edition)
Canonical book for recurrence-solving technique, built from Knuth's Stanford course. Chapter 1 solves recurrent problems such as the Tower of Hanoi and the Josephus problem; Chapter 7 solves recurrences with generating functions. Includes hundreds of exercises with answers.
Mathematics for Computer Science (Recurrences chapter)
Free MIT 6.042J textbook. Its Recurrences chapter covers the Towers of Hanoi, merge sort, linear recurrences solved by characteristic roots, divide-and-conquer recurrences and the Akra-Bazzi method, and guessing-and-verifying by induction; a later chapter covers generating functions. Bridges recurrences to algorithmic complexity with proofs and problem sets.