--- title: Recurrence Relations description: Recurrence relations are equations that define sequences recursively using previous terms. Learners will understand how to solve these relations using characteristic equations and generating functions to model algorithmic complexity and population growth. category: mathematics subcategory: combinatorics difficulty: beginner, intermediate, advanced url: /subject/recurrence-relations --- # Recurrence Relations Recurrence relations are equations that define sequences recursively using previous terms. Learners will understand how to solve these relations using characteristic equations and generating functions to model algorithmic complexity and population growth. ## Where to start Start with Art of Problem Solving, whose free wiki and forum threads work through recurrences in combinatorics problems at a beginner level. If you only use one resource, make it Mathematics for Computer Science (MIT 6.042J) by Tom Leighton and Marten van Dijk, a full free course with lecture videos, problem sets and exams on discrete mathematics, including asymptotics and counting. ## Available Resources 4 Books • 3 Courses • 2 Websites ## Websites ### 1. 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. **Difficulty:** Beginner | **Price:** Free **Link:** https://artofproblemsolving.com/wiki/index.php/Recurrence_relation **Tags:** recurrence-relations, characteristic-polynomial, competition-math, combinatorics ### 2. Wolfram MathWorld **Author:** Eric W. Weisstein 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. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://mathworld.wolfram.com **Tags:** mathematics-reference, encyclopedia, abstract-algebra, number-theory, geometry ## Courses ### 1. Mathematics for Computer Science (MIT 6.042J) **Author:** Tom Leighton, Marten van Dijk 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. **Difficulty:** Intermediate | **Price:** Free **Link:** https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/ **Tags:** discrete-mathematics, mathematical-proofs, induction, graph-theory, combinatorics, discrete-probability ### 2. Analysis of Algorithms (Coursera) **Author:** Robert Sedgewick 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. **Difficulty:** Advanced | **Language:** English | **Price:** Free **Link:** https://www.coursera.org/learn/analysis-of-algorithms **Tags:** analysis-of-algorithms, recurrence-relations, generating-functions, asymptotics, analytic-combinatorics ### 3. Discrete Mathematics **Author:** Dominik Scheder Dominik Scheder's proof-based course on sets, functions and relations, enumerative combinatorics, graph theory, and network flows and matchings, each concept paired with a fully proved non-trivial result. Learners read formal statements and write rigorous proofs of their own. **Difficulty:** Intermediate | **Language:** English | **Duration:** 11 weeks of study, 3-5 hours per week. | **Price:** Free **Link:** https://www.coursera.org/learn/discrete-mathematics **Tags:** discrete-math, combinatorics, graph-theory, network-flows, proofs ## Books ### 1. generatingfunctionology **Author:** Herbert S. Wilf 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. **Difficulty:** Advanced | **Language:** English | **Price:** Free **Link:** https://www2.math.upenn.edu/~wilf/DownldGF.html **Tags:** generating-functions, recurrence-relations, combinatorics, formal-power-series, asymptotics ### 2. Concrete Mathematics: A Foundation for Computer Science (2nd Edition) **Author:** Ronald L. Graham, Donald E. Knuth, Oren Patashnik 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. **Difficulty:** Advanced | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/0201558025?tag=edmonddante07-20 **Tags:** recurrence-relations, generating-functions, discrete-mathematics, sums, combinatorics ### 3. Mathematics for Computer Science (Recurrences chapter) **Author:** Eric Lehman, F. Thomson Leighton, Albert R. Meyer 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. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://courses.csail.mit.edu/6.042/spring18/mcs.pdf **Tags:** recurrence-relations, discrete-mathematics, divide-and-conquer, akra-bazzi, proofs ### 4. Discrete Mathematics: An Open Introduction — Section 2.4: Solving Recurrence Relations **Author:** Oscar Levin 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. **Difficulty:** Beginner | **Language:** English | **Price:** Free **Link:** https://discrete.openmathbooks.org/dmoi3/sec_recurrence.html **Tags:** recurrence-relations, discrete-math, characteristic-root-technique, closed-formulas, open-textbook --- *This content is part of Dantes.io - Your Treasure Map to Knowledge* *Curated by humans at Dantes.io. Personal study use welcome; republishing this curation requires permission (team@dantes.io).* View this page online: https://dantes.io/subject/recurrence-relations