Lecture 9: Solving Recurrence Equations continued

Sick of ads?‚Äč Sign up for MathVids Premium
Taught by ArsDigita
  • Currently 3.0/5 Stars.
5460 views | 1 rating
Lesson Summary:

In this lesson on solving recurrence equations, we learn about linear homogeneous recurrence relations with constant coefficients and their applications in analyzing algorithms. The characteristic equation associated with the recurrence equation gives us roots, and we can use these roots to find a formula for the nth term of the sequence. The initial conditions allow us to solve for the constants in the formula. Through the use of substitution, we can see the pattern in the sequence and use that to guess the form of the solution.

Lesson Description:

More on solving recurrence equations.

More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/

Additional Resources:
Questions answered by this video:
  • How can you find the time complexity for an algorithm that uses recursion?
  • What is a linear homogeneous recurrence equation with constant coefficients of degree k?
  • How do you find a closed formula for a sequence?
  • How do you find the roots of a characteristic equation and what do they tell you?
  • How do you solve a system of linear recurrence equations?
  • What is a nonhomogeneous recurrence equation, and how do you solve it?
  • Staff Review

    • Currently 3.0/5 Stars.
    This recitation reviews some concepts of recursion and recurrence equations. Some example problems are done for problems similar to those covered in lectures. This is a good video to watch for some more example problems to clear up you thinking and understanding of these particular topics, but not much new is discussed and it is rather dry.