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