Definition: Linear Homogeneous Recurrence Relation
A linear homogeneous relation of degree 4k$ with constant
coefficients is a recurrence relation of the form
where are real
numbers, and .
By induction, such a recurrence relation is uniquely determined by
this recurrence relation, and
initial conditions .
Assume that the sequences
and both satisfy the
recurrence, then ,
also satisfy the
recurrence, where is a
constant. This means if we find some solutions to a linear homogeneous
recurrence, then any linear combination of them will also be a
solution.
So we need to find any solution of the form that satisfies the recurrence,
where is a constant. Then we
substitute this back into the recurrence: So the solutions to the characteristic equation can
yield an explicit formula for the sequence:
Consider an arbitrary linear homogeneous relation of degree 2 with
constant coefficients: The characteristic equation is then
Theorem
If this CE has 2 roots , then the sequence is a solution of the recurrence
iff
for and constants .
The two constants can be obtained by
solving equation w.r.t. the initial conditions. We may generalize this
theorem to degree :
Theorem
Consider an arbitrary linear homogeneous relation of degree with constant coefficients The
characteristic equation is then If this CE
has distinct roots , then the solutions to the recurrence
are of the form for all
, where the ’s are constants.
If the CE has degenerate roots:
Theorem
If the CE has
only root , then for all
and two constants and .
Example
Solve
with initial conditions ,
.
Solution. The CE is The only root is . So we
assume that, By the two initial conditions, we have and . Thus,
We generalize the theorem to degree :
Theorem
Suppose that there are roots
with multiplicities
. Then
for all and constants .
Linear
Nonhomogeneous Recurrence Relations
Definition: Linear Nonhomogenous Recurrence Relation
A linear nonhomogenous relation with constant coefficients
may contain some terms that
depend only on
The recurrence relation
is called the associated homogenous recurrence relation.
Assume that the sequence
satisfies the recurrence. Then another sequence satisfies the nonhomogenous
recurrence iff is a
sequence that satisfies the associated homogenous recurrence.
Since we already know how to find . For many common , a solution to the nonhomogenous recurrence is
similar to . We then need find
to the nonhomogeneous
recurrence that satisfies both recurrence and initial conditions.
Theorem
If is any particular
solution to the linear nonhomogenous relation with constant
coefficients,
Then all its solutions are of the form where is any solution to the
associated homogenous recurrence relation
Example
Solve with
initial condition .
Solution. The CE of the associated linear homogeneous
recurrence relation is Thus, the solution to the original problem is of the form
We try a degree-
polynomial as the particular solution . Let , then So we have and . Thus, and the solution is
Example
Consider the linear nonhomogeneous recurrence relation for the Tower
of Hanoi problem:
with .
Solution. The CE of the associated homogenous recurrence
relation is . Thus, the
solution to the original problem is of the form We try a constant as
the particular solution . Then
So the solution is
Example
Consider the linear nonhomogeneous recurrence relation for the merge
sort: with
.
Solution. Let , then we have with . The CE of
the associated linear homogeneous recurrence relation is . Thus, the solution to the
original problem is of the form We try as the
particular solution . Then
which gives . So
we get . With the initial condition we have
