14.3. General Method for Solving Recurrence Equations

Try these first

1. 1.

   What is a linear homogeneous recurrence equation?

   Hint

   Think of the Fibonacci sequence.

2. 2.

   Identify the characteristic equation for T(n) = 3T(n-1) + 2T(n-2).

   Hint

   Follow the structure of r^2 - ar - b.

3. 3.

   What form does a linear homogeneous recurrence equation take?

   • T(n) = a*T(n-1) + b*T(n-2)
   • T(n) = a*T(n-1) + b
   • T(n) = an^2 + bn + c

   Hint

   Look for terms that rely only on previous values.

4. 4.

   True or False: The characteristic equation provides the exact solution to the recurrence relation.

   • True
   • False

   Hint

   Think about what other information is needed.

5. 5.

   Solve the recurrence relation T(n) = 3*T(n-1) - T(n-2) with T(0) = 5 and T(1) = 10. Demonstrate the steps.

   Hint

   Remember to use the quadratic formula!

6. 6.

   Consider a sequence defined by T(n) = T(n-1) + 4*T(n-2) - T(n-3). How would you approach solving for T(n) using the characteristic equation? Present your method.

   Hint

   Factor or use the quadratic formula for the eigenvalues!