โ Discrete Mathematics learning pathDiscrete Mathematics ยท Module 7 of 10
Recurrence relations
Sequences defined by earlier terms.
๐ Key ideas
- A recurrence defines a term from previous terms: Fibonacci F(n) = F(n - 1) + F(n - 2).
- Linear homogeneous recurrences are solved with the characteristic equation.
- a(n) = 2 a(n - 1) with a(0) = 1 gives a(n) = 2^n.
- Divide-and-conquer algorithms give recurrences such as T(n) = 2T(n/2) + n, solved by the master theorem.
- Generating functions are another method for solving recurrences.
๐ก Real-life example: A recurrence is like compound interest: this year's amount is defined by last year's amount.
Recurrence relationEquation defining a term from earlier terms
Characteristic equationPolynomial used to solve linear recurrences
Master theoremSolves divide-and-conquer recurrences
Initial conditionStarting values of a recurrence