Explore the concept of solving linear homogeneous recurrence relations with examples and explanations. Learn about closed-form solutions, induction, characteristic equations, and more in the context of sequences and functions defined by recurrence relations.
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
Recurrence Relations to Define a Sequence g0 = 1 For n 2, gn= 2 gn-1+ 1 A closed form solution for a recurrence relation, gives the nthterm in the sequence as a function of n, not as a function of earlier terms: For n 0, gn= 2n+1- 1
Induction and Recurrence Relations We used inductive to verify that a formula was a correct closed form solution for a sequence defined by a recurrence relation. Now we will show how to solve recurrence relations without knowing the formula in advance ..(for a particular class of recurrence relations).
Linear Homogeneous Recurrence Relations Linear: the coefficient of each term is a constant. gn= 3gn-1+ 2gn-2+ n2 (linear) gn= 3(gn-1)2+ 2gn-2+ n2 gn= 2gn-1 gn-2+ n2 (not linear) gn= n gn-2+ n2 (not linear) (not linear) Homogeneous: no additional terms that do not refer to earlier numbers in the sequence. gn= 3gn-1+ 2gn-2 (homogeneous) gn= 3gn-1+ 2gn-2+ n2 (not homogeneous)
Linear Homogeneous Recurrence Relations A linear homogeneous recurrence relation has the form: fn = c1 fn-1 + c2 fn-2+ . + cd fn-d c1, c2, , cd are constants If cd 0, degree d recurrence relation
Linear Homogeneous Recurrence Relations Always has a solution of the form fn = xn. Plug into the recurrence and solve for x: fn = 5fn-1 6fn-2
Linear Homogeneous Recurrence Relations Characteristic equation for fn = 5fn-1 6fn-2 is x2 5x + 6 = 0 (degree d recurrence relation -> characteristic equation is a degree d polynomial) Roots: x = 2, x = 3. (Case: distinct, real roots) Solutions: fn = 2n and fn =3n
Linear Homogeneous Recurrence Relations Any linear combination fn = 1 2n + 2 3n satisfies: fn = 5fn-1 6fn-2 fn = 1 2n + 2 3n is called the general solution of the recurrence relation fn = 5fn-1 6fn-2
Initial Conditions Initial conditions narrow down the possibilities to one sequence fn = 5fn-1 6fn-2
Initial Conditions Initial conditions are used to solve for the constants 1 and 2 infn = 1 2n + 2 3n f0 = 3 f1 = 8
Linear Homogeneous Recurrence Relations 1. Plug in fn = xn to get characteristic equation 2. Solve for roots of characteristic equation. 3. Set up general solution. 4. Use initial conditions to set up linear equations to solve for constants in general solution: Degree d recurrence relation -> degree d characteristic equation -> d constants (unknown coefficients) in general solution d initial conditions -> d equations.
Linear Homogeneous Recurrence Relations: degree 3 example Plug in gn = xn to get characteristic equation 1. gn = 4gn-1 gn-2 6gn-3 g0 = 5 g1 = 0 g2 = 18
Linear Homogeneous Recurrence Relations: degree 3 example 2. Solve for roots of characteristic equation. 3. Set up general solution.
Linear Homogeneous Recurrence Relations: degree 3 example 4. Use initial conditions to set up linear equations to solve for constants in general solution: gn = 1 3n + 2 2n + 3 (-1)n g0 = 5 g1 = 0 g2 = 18
Linear Homogeneous Recurrence Relations: degree 3 example 5. Solve linear equations for coefficients and plug back in to general solution to get the specific solution for this sequence.
