Finding an Explicit Formula for a Recursive SeriesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/