Recursive and Explicit FormulasDate: 01/19/99 at 23:58:02 From: Dawn Ososke Subject: Recursive and Explicit formulas Is there an easy way to convert recursive formulas into explicit ones and vice versa? I've studied the examples in my pre-calculus book, but all of the examples are easy-to-solve problems, unlike the ones I will have to solve on the test. I've tried figuring out the first ten or so numbers in a particular sequence, but rarely can I see a pattern that I can put into a formula. Date: 01/20/99 at 13:18:24 From: Doctor Rob Subject: Re: Recursive and Explicit formulas In general, this is a fairly difficult problem. There are easy cases, but there are hard cases, and there are unsolved (and possibly unsolvable) cases, too. The situation is analogous to the situation when you are faced with a differential equation (analogue of a recursion) or an explicit equation for a function (analogue of the formula). Let the sequence be S(1), S(2), .... Some of the cases where you can find the formula given the recursion are: 1. Recursions that are sums of terms like c(i)*S(n-i), where c(i) are constants, like the Fibonacci recursion: S(n) = 1*S(n-1) + 1*S(n-2). 2. As in (1), but you can also have a term which is a polynomial in n, like S(n) = 2*S(n-1) + n. 3. Things like S(n) = S(n-1)^c, where c is a constant. There are lots of others, too. If you start with a formula and want to find a recursion, it is a good idea to write out S(n), S(n-1), S(n-2), and try to see some part of the first formula that is actually equal to one of the other formulas. For example, if: S(n) = n*2^n, S(n-1) = (n-1)*2^(n-1), etc. then you can see that the second formula can be converted into the first by multiplying by (2*n)/(n-1), so S(n) = [(2*n)/(n-1)]*S(n-1), S(1) = 2 is a recursion which this formula satisfies. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/