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/