CS202: Discrete Structures

7.2: Solving Recurrence Relations

• University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions and Graphs: Decision Trees and Recursion" URL

  Read from example 27 to the end of the chapter on pages DT-46 - DT-50

  A solution to a recursive equation is a formula that computes A(n) without having to compute A(k), for k < n. Review the section on "Recursive Equations," on page DT-44 up to example 26 on page DT-46.

  1. A solution to a recursive equation can be found by inspection of the terms of a given sequence (example 27); OR
2. Apply theorem 8 if A(n) depends on A(n - 1) and theorem 9, if A(n) depends on A(n - 1) and A(n - 2).

  Regarding Theorem 8 on page DT-48, if a_n = ba_n - 1 +c , then iterating, a_n = b( ba_{n - 2}+c) + c = b(b (b a_{n - 3}+ c ) + c ) + c= ....= a₀ b_n + c b_n-1 + c b_n-2 + .... + c. This is an example of using the method of iteration for finding a formula for a recurrence relation for an arithmetic sequence.
  

• 7.2.1: Finding a Formula for an Iterative Relation for a Geometric Sequence

  • University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions and Graphs: Decision Trees and Recursion" URL

    A simple example of going from an iterative relation to a formula is as follows: given the iterative relation, a_n = ar_n , ar_n, = r a r _n-1 = r a _{n - 1}, . Continuing in this manner, we get the formula, an = r_n a₀.

    For another example, read over Exercise 4.7 on page DT-51. It discusses going from an iterative sequence to a recursive solution/equation, and vice versa, from the recursive equation to an iterative sequence.

  • Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Sums and Approximations" URL

    Note that you have already read this lecture in Subunit 4.2. Focus on re-reading Section 1.2 on page 3, which finds a formula not for the terms of the sequence, but for the sum of the terms of the sequence.

• 7.2.2: Using Mathematical Induction

  • University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions and Graphs: Decision Trees and Recursion" URL

    Read Section 4 on pages DT-42 to DT-44 up to "Recursion Equations." Note that mathematical induction and recursion are closely related concepts.