**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:

=