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
_____________________________________________

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
                    -------------     adding
                     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

[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/