8.2 Solving Linear Recurrence Relations

Question 1

Recurrence Relation

Answer 1

The rule in a recursive definition describing how to obtain subsequent terms of a sequence using previous terms

Question 2

First term

Answer 2

Depends only on one previous term (degree 1)

Question 3

Meaning of linear

Answer 3

The right hand side is a sum of previous terms of the sequence

Question 4

Meaning of homogenous

Answer 4

All coefficients are constants rather than functions that depend on n and F(n) = 0

Question 5

What is the goal when finding explicit formulas

Answer 5

To write the function an = something not relying on a previous term(an-1)

Question 6

Steps to find solution of homogeneous recurrence relations

Answer 6

1. Find characteristic equation (r^k - c1r^(k-1) - … -ck=0)
2. Solve for roots
3. Find an = α1r1^n + α2r2^n + … + αkrk^n =0
4. Find α0, α1, αk using initial conditions a0, a0, ak..
5. Find solution by substituting into an = α1r1^n + α2r2^n + … + αkrk^n =0

Question 7

Steps to find solutions of nonhomogeneous recurrence relations

Answer 7

1. Use general form of polynomials to find an(p) for the homogeneous recurrence
2. Find the homogeneous recurrence relation an(h) (without F(n)) and solve it normally by finding α
3. Find the general solution where an = an(p) + an(h)
4. Use the initial condition to find the unique solution