Transcript 08_SolvingLinearHomogeneousRecurrenceRelationsx

Solving Linear Homogeneous
Recurrence Relations
ICS 6D
Sandy Irani
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 nth term 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 (not linear)
gn = 2gn-1·gn-2 + n2 (not linear)
gn = n·gn-2 + n2 (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?
• gn = 3gn-1 + 4gn-2 + n2
• gn = 3gn-1 + (gn-2)/5
• gn = 3gn-1 + 2
• gn = log(2)·gn-2 + 5 gn-7
• gn = n·gn-2 + 5 gn-7
• gn = gn-1·gn-2 + 5 gn-7
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 in fn = α1·2n + α2·3n
• f0 = 3
• f1 = 8
Linear Homogeneous
Recurrence Relations
1.
2.
3.
4.
Plug in fn = xn to get characteristic equation
Solve for roots of characteristic equation.
Set up general solution.
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
1. Plug in gn = xn to get characteristic equation
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.
Linear Homogeneous Recurrence
Relations: non-distinct roots
gn = 6gn-1 – 9gn-2
g0 = 1
g1 = 6
Non-distinct roots:
Check solution
Check that gn = n3n is a solution to gn = 6gn-1 – 9gn-2
Linear Homogeneous Recurrence
Relations: non-distinct roots
gn = 6gn-1 – 9gn-2 general solution: gn = α1·3n + α2·n3n
g0 = 1
g1 = 6
General solution with
non-distinct roots:
Characteristic equation for {fn}:
(x – r)m = 0
General solution:
fn = α1·rn + α2·n·rn+ α3·n2·rn + α4·n3·rn + …. + αm·nm-1·rn
General solution with
non-distinct roots:
Characteristic equation for {fn}:
(x – 4)3 (x + 1)2 (x – 5) = 0
General solution:
Example
gn = 5gn-1 – 8gn-2+ 4gn-3
g0 = 5
g1 = 6
g2 = 6