Linear Recurrance Relations

Date: 08/10/2004 at 16:04:03
From: Kevin
Subject: Turning Recursive/Iterative(?) Equations into Functions

There are some things that are described by running a value through
the same equation repeatedly.  I think this is called both "iteration"
and "recursion."  Is there a general way to turn such an equation into
a normal continuous function?  If not, are you aware of any specific
hints?

Ex: x_(n+1) = x_n + 1, if seed(x_0) = 0, then 0,1,2,3,4,5...
          y = x  (n->x)

Ex: x_(n+1) = (1/3)*(x_n), if seed 1, then 1,(1/3),(1/9),(1/27)...
          y = 1/(3^x)

Ex: x_(n+1) = (1/3)*(x_n) + 1, if seed 1, then 1,(4/3),(13/9)...
          y = ???

Ex: x_(n+1) = x_n - ((-1^n)/(2n-1)), if seed 0, then 0,1,(2/3)...
          y = ???

Some of them are easy, like the first two, because I recognize the
progression.  I'm completely at a loss for the others, though.

Date: 08/10/2004 at 16:58:07
From: Doctor Vogler
Subject: Re: Turning Recursive/Iterative(?) Equations into Functions

Hi Kevin,

Thanks for writing to Dr. Math.  These are called "recurrence
relations" and there has been much study devoted to them.  There are a 
variety of techniques that apply to different kinds of recurrence 
relations.  Some recurrence relations are simply too complicated, and 
there is no way to write out a simple formula for them, which is 
called writing an "explicit formula" in "closed form."

About notation, we would generally say that:

  x_(n+1) = x_n + 1

implies that

  x_n = n + x_0.

So it is preferable not to change your n into x, especially since you
were already using x as the value of the recurrence (changed to y in
the next line) rather than the index (n).

That said, a "(homogeneous) linear recurrence relation" is one like:

  2*x_(n+3) + 5*x_(n+2) - x_(n+1) + 3*x_n = 0,

where you multiply each x_(n+i) value by some constant, any real
number, and you sum them all up and get zero.  (Or you might have some
on the left side of the equation and some on the right, but that's the
same thing.)  Your second case is a linear recurrence relation, and
they are rather simple:  Change x_(n+i) into r^i and you will get a
polynomial, like

  2*r^3 + 5*r^2 - r + 3 = 0,

find its roots (such as r1, r2, and r3), and x_n has the form

  a1 * r1^n + a2 * r2^n + a3 * r3^n

where the constants a1, a2, a3 (up to the degree of the polynomial)
are determined by the initial values (seeds, you called them) of the
sequence.  There is more math that can be said about this, but it
gives you the idea.

Your other three examples are "nonhomogeneous linear recurrence
relations," which means that they would be linear except that instead
of having everything equal zero, it equals some function of n (your
index variable).  In that case, you find all solutions by starting
with the homogeneous equation (removing the function of n) and getting
the "general solution" from that.  And then you add any one
"particular solution" of the nonhomogeneous equation.  For example,

  x_(n+1) = (1/3)*x_n + 1,

or

  x_(n+1) - (1/3)*x_n = 1

corresponds to the homogeneous equation

  x_(n+1) - (1/3)*x_n = 0

which corresponds to the polynomial

  r - 1/3 = 0

which has root r = 1/3, and so your "general solution" (to the
homogeneous equation) is:

  x_n = a * (1/3)^n

for any constant number a (determined by the initial value or seed). 
Then we need one "particular" solution to the nonhomogeneous equation,

  x_(n+1) - (1/3)*x_n = 1,

and there are a variety of techniques for finding them, but the
easiest idea is to guess that it will have a form similar to the
function on the right (in this case, a constant number) and then solve
for the constants or coefficients.  If x_n is a constant b, then

  b - (1/3)*b = 1,

and b = 3/2.  So then we add the two pieces together and find that all
solutions to the nonhomogeneous equation

  x_(n+1) - (1/3)*x_n = 1

are

  x_n = 3/2 + a * (1/3)^n.

By substituting the initial condition x_0 = 1, we can solve for a:

  1 = x_0 = 3/2 + a * (1/3)^0 = 3/2 + a
  1 = 3/2 + a  
  a = -1/2

so

  x_n = 3/2 - 1/2 * (1/3)^n.

For your last example, there is no simple explicit formula for x_n,
but you can write it as a sum:

              n-1
  x_n = x_1 - sum (-1^i)/(2i-1)
              i=1

For more information, search for the terms "linear recurrence 
relation", "nonhomogeneous linear recurrence relation", or just
"recurrence relation" on our archives or on the internet.  There is a
lot of information available about all of those.

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/