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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.