Associated Topics || Dr. Math Home || Search Dr. Math

### Finding an Explicit Formula for a Recursive Series

```
Date: 05/17/2000 at 03:47:43
From: Jacob Phillips
Subject: Explicit formula for a recursive sequence

My question is as follows:

There was a man who couldn't decide in which direction he wanted to
walk, but there was a method in his indecision. He started off walking
a mile west from his home. Then he changed his mind and walked back
east one half the distance. He then changed his mind again and walked
west again half of the distance he had just walked, and so on. (1,
1/2, 1/4, 1/8, 1/16, ...) The question is, how far away did he end up
from his home?

The distance the man is from home each time he changes his mind can be
thought of as terms in an alternating sequence. The first few terms
are:

for n = 1:    1    mile
for n = 2:   1/2   mile      (1 - 1/2)
for n = 3:   3/4   mile    (1/2 + 1/4)
for n = 4:   5/8   mile    (3/4 - 1/8)
for n = 5:  11/16  mile    (5/8 + 1/16)
for n = 6:  21/32  mile    (5/8 - 1/32)
for n = 7:  43/64  mile  (21/32 + 1/64)
for n = 8:  85/128 mile  (43/64 - 1/128)
for n = 9: 171/256 mile (85/128 + 1/256)

and so on.

The denominators of these distances are 2^n. But the numerators have
got me. I know that the terms in the numerator can be represented by
the recursive sequence:

f_n = f_(n-1) + 2*f_(n-2)

This is close to the recursively defined Fibonacci sequence:

f_n = f_(n-1) + f_(n-2)

I saw another question on your wonderful Web site where the explicit
formula was found from the auxiliary equation k^2 = k + 1

f_n = phi^n/sqrt(5) - (1-phi)^n/sqrt(5)

where phi is the golden ratio. (I don't know how to do 2nd order
differential equations.)

So I need a formula to generate the nth term for the numerators:
1, 1, 3, 5, 11, 21, 43, 85, 171, ..., n.

The limit as n goes to infinity of (?)/2^n should be the answer...
right?

Respectfully,
Jacob
```

```
Date: 05/17/2000 at 07:14:57
From: Doctor Anthony
Subject: Re: Explicit formula for a recursive sequence

To find the nth term for the recurrence relation

u(n+2) - u(n+1) - 2u(n) = 0

we consider the auxiliary equation

x^2 - x - 2 = 0

(x-2)(x+1) = 0

with roots -1 and 2. We then can say that

u(n) = A.(-1)^n + B(2^n)

u(1) = 1   so   1 = -A + 2B
u(2) = 1   so   1 =  A + 4B
2 =      6B
and so

B = 1/3
and
A = 1 - 4B = 1 - 4/3 = -1/3

Therefore

u(n) = (-1/3)(-1)^n + (1/3)(2^n)

Check n = 3: u(3) = +1/3 + 8/3 = 9/3 = 3        (okay)

Check n = 7: u(7) = +1/3 + 128/3 = 129/3 = 43   (okay)

Check n = 8: u(8) = -1/3 + 256/3 = 255/3 = 85   (okay)

So our formula is giving the correct sequence. We can be certain that
the formula for u(n) is

u(n) = (-1/3)(-1)^n + (1/3)(2^n)

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
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