Nonhomogeneous Linear Recurrence Relations

Date: 05/18/2004 at 05:02:26
From: Raul
Subject: find linear recurrence relation

Given a recursive formula: a(n+1) = a(n) + (a(n) - b)*t, where b is a
known constant and a(1) is also known, I am trying to find the 
explicit formula like y = ????? * t^n.

I have tried to look for the "fixed point" which is what a(n) would 
be if a(n+1) = a(n), 

  a(n) = a(n) + (a(n) - b)*t

However this doesn't seem to give anything useful:

  0 = (a(n) - b)*t

Any help would be appreciated.

Date: 05/18/2004 at 09:58:48
From: Doctor Vogler
Subject: Re: find linear recurrence relation

Hi Raul,

Thanks for writing to Dr. Math.  What you have is a nonhomogeneous
linear recurrence relation.  You solve those in two parts.  First you
write it as

  a(n+1) - (t+1)*a(n) = -b*t

to separate the homogeneous part (on the left) from the leftover
"forcing" term (on the right).  Now you find the general solution of
the homogeneous part on the left by solving the equation

  x^(n+1) - (t+1)*x^n = 0

and you get x = t+1, which means you have the general solution to the
homogeneous part a(n) = C*(t+1)^n, where C is some (as yet unknown)
constant.  (You'll notice that you can substitute this into your
equation and get a solution when b = 0, when it is homogeneous.)  Next
you find a single particular solution by choosing a likely form

  a(n) = constant = k

(since the forcing term is a constant) and seeing what the constant
has to be.

  a(n+1) - (t+1)*a(n) = -b*t
          k - (t+1)*k = -b*t
                 -t*k = -b*t
                    k = b

which is actually the fixed point that you were looking for before. 
You had gotten

  0 = (a(n) - b)*t

and then stopped.  But if you divide by t and solve for a(n), you find
that the fixed point is at a(n) = b (unless t = 0, in which case every
point is fixed).

Then the general solution is the sum of the general homogeneous
solution and the particular solution

  a(n) = C*(t+1)^n + b

and we choose C according to what a(1) is.  Since

  a(1) = C*(t+1) + b,

we must have

  C = (a(1) - b)/(t+1),

and therefore

  a(n) = (a(1) - b)*(t+1)^(n-1) + b.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to 
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/18/2004 at 11:00:10
From: Raul
Subject: find linear recurrence relation

Thank you very much.  I could follow everything except for the forcing
term.  Why is a(n+1) = a(n) = constant = k?

From your formulas:

  a(n+1) - (t+1)*a(n) = -b*t 
          k - (t+1)*k = -b*t 

Regards,

Raul

Date: 05/18/2004 at 11:27:51
From: Doctor Vogler
Subject: Re: find linear recurrence relation

Hi Raul,

When you want to find a "particular" solution to a nonhomogeneous
linear recurrence relation, you generally guess the form of the
solution, pack it full of unknowns, and then solve for what the 
unknowns need to be.  The idea of a "particular" solution is that you
only need any one solution, since every other solution will be your
solution plus a solution to the homogeneous recurrence (this is not
hard to prove; can you prove it?).  So you figure what is my solution
most probably going to look like, and you try it.

For example, if I wanted a particular solution to

  a(n+2) + 2a(n+1) + 3a(n) = n^2 + 2n + 3,

then I would probably guess that some polynomial of degree no more
than 2 will work, so I try

  a(n) = a*n^2 + b*n + c

and then I substitute that into my formula and solve for the 
coefficients a, b, and c.  There are several techniques to picking the
form of your particular solution, such as:  If some expression appears
in the "forcing term," then put it in the particular solution,
multiplied by a constant.  If some polynomial (like n^3) appears in
the forcing term (even if multiplied by something nonpolynomial), then
don't just include that term but also all terms of lower degree (a*n^3
+ b*n^2 + c*n + d).  If one of these rules says to include a certain
term, but that term already appears in the general solution to the
homogeneous problem, then multiply the term by n.

Sometimes none of these will give you a particular solution, but they
work well for most simple examples.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/18/2004 at 11:44:35
From: Raul
Subject: Thank you (find linear recurrence relation)

Thank you very much.