Discrete Mathematics: An Open Introduction — Section 2.4: Solving Recurrence Relations
by Oscar Levin · University of Northern Colorado (open textbook)
Free open-textbook section covering telescoping, iteration, and the characteristic root technique for linear homogeneous recurrences, including the repeated-root case, with worked examples, checks of closed formulas, and exercises with hints.
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.
Analysis of Algorithms (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.
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.