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
Math Forum Home || Math Library || Quick Reference || Math Forum Search