CS 171 Linear Nonhomogeneous Recurrences with Constant Coefficients
This is a recurrence of the form:
=
Associated homogeneous recurrence:
=
Theorem: Suppose
is a particular solution to the above non-homogeneous
recurrence. Then each solution
to the nonhomogeneous recurrence can
be written as
where
is a solution to the associated
homogeneous recurrence.
proof: Let
=
where
is as described above. Then
=
=
=
=
Thus any such
=
is a solution to the nonhomogeneous rec.
2nd part of proof: Suppose
is any solution to the nonhomogeneous rec.
=
=
=
Let
=
The above line says that it is a solution to the
associated homogeneous recurrence. Note that
=
as desired.
Example:
=
Thus
=
=
a) Solve the associated homogeneous recurrence
=
Characteristic equation is
=
with solution
=
Thus
=
is the general solution to the homog. rec.
b) Find a particular solution to the nonhomog. rec.
Try
=
=
Substituting this into the nonhomog. recurrence gives:
=
=
=
Since this polynomial in n is always 0, the coefficients must be zeros:
=
and
=
=
=
=
=
Thus the general form of the solution to the nonhomog. rec. is
=
c) Apply the initial condition(s)
=
gives
=
=
=
Answer:
=
Example:
=
Thus
=
=
a) Solve the associated homogeneous recurrence
=
Characteristic equation is
=
with solution
=
Thus
=
=
is the general solution to the homog. rec.
b) Find a particular solution to the nonhomog. rec.
Try
=
=
since 1 is a root of the
char. eq.
Substituting this into the nonhomog. recurrence gives:
=
=
=
Since this polynomial in n is always 0, the coefficients must be zeros:
=
and
=
=
=
=
Thus the general form of the solution to the nonhomog. rec. is
=
=
c) Apply the initial condition(s)
=
gives
=
so that
=
Answer:
=
Question: What is this a recurrence for?
Answer: This is clearly a recurrence for
=
and we got the standard formula for this sum as our answer.
Example:
=
Thus
=
=
=
a) Solve the associated homogeneous recurrence
=
Characteristic equation is
=
=
which has solutions
=
and
=
Thus
=
is the general solution to the homog. rec.
b) Find a particular solution to the nonhomog. rec.
Try
=
=
since 2 is a root of the
char. eq. with mult. 1
Substituting this into the nonhomog. recurrence gives:
=
Divide both sides by
to get:
=
=
=
=
Since this polynomial in n is always 0, the coefficients must be zeros:
=
and
=
=
=
=
Thus the general form of the solution to the nonhomog. rec. is
=
=
c) Apply the initial condition(s)
=
gives
=
=
=
=
gives
=
so
=
Then
=
=
=
Answer:
=
=
Example:
=
=
Thus
=
a) Solve the associated homogeneous recurrence
=
Characteristic equation is
=
with solution
=
Thus
=
is the general solution to the homog. rec.
b) Find a particular solution to the nonhomog. rec.
Since our function F(n) is the sum of 2 functions of the type we normally
deal with, let's work with each separately and then use linearity to say that
the desired particular solution is the sum of the 2 particular solutions found
in our 2 separate problems.
First find on a particular solution to
=
Try
=
=
Substituting this into the first nonhomog. recurrence gives:
=
=
=
Since this polynomial in n is always 0, the coefficients must be zeros:
=
and
=
=
=
=
Our first particular solution is thus
=
Then find on a particular solution to
=
Try
=
Substituting this into the second nonhomog. recurrence gives:
=
Divide both sides by
to get:
=
so that
=
Our second particular solution is thus
=
Hence a particular solution to
=
is the sum of the above particular solutions:
=
Thus the general form of the solution to the original nonhomog. rec. is
=
c) Apply the initial condition(s)
=
gives
=
so
=
Thus
=
Answer:
=
