Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Recursive and Explicit Formulas


Date: 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/   
    
Associated Topics:
High School Discrete Mathematics
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/