โ† Discrete Mathematics learning path
Discrete Mathematics ยท Module 7 of 10

Recurrence relations

Sequences defined by earlier terms.

๐Ÿ“– Key ideas

  1. A recurrence defines a term from previous terms: Fibonacci F(n) = F(n - 1) + F(n - 2).
  2. Linear homogeneous recurrences are solved with the characteristic equation.
  3. a(n) = 2 a(n - 1) with a(0) = 1 gives a(n) = 2^n.
  4. Divide-and-conquer algorithms give recurrences such as T(n) = 2T(n/2) + n, solved by the master theorem.
  5. 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