December 17th, 2010, 08:39 PM  #1 
Newbie Joined: Dec 2010 Posts: 11 Thanks: 0  Recurrence relation
Hi I don't quite understand how to write a recurrence formula out of recurrence relation. Can someone explain in detail all the steps of forming of Fibonacci sequence as an example? Including the use of t^2AtB=0 equation, distinct root theorem etc. Thanks in advance. 
December 17th, 2010, 10:40 PM  #2 
Senior Member Joined: Jul 2010 From: St. Augustine, FL., U.S.A.'s oldest city Posts: 12,211 Thanks: 520 Math Focus: Calculus/ODEs  Re: Recurrence relation
The Fibonacci sequence is recursively defined as: with seed values and . If we assume a solution of the form and substitute into the recursion formula, we have: Dividing through by . we have: yielding the characteristic equation: whose roots are Since these roots are distinct, we have the general solution: Using our seed values, we obtain the system: Solving, we find: and thus we have: For information on the theorems involved see: http://en.wikipedia.org/wiki/Recurrence_relation http://en.wikipedia.org/wiki/Fibonacci_number 
December 17th, 2010, 10:49 PM  #3 
Newbie Joined: Dec 2010 Posts: 11 Thanks: 0  Re: Recurrence relation
Thanks for your reply. I've got a question though. The seed values F0 = 0 and F1 = 1. Where are they used? 
December 17th, 2010, 10:55 PM  #4 
Senior Member Joined: Jul 2010 From: St. Augustine, FL., U.S.A.'s oldest city Posts: 12,211 Thanks: 520 Math Focus: Calculus/ODEs  Re: Recurrence relation
We obtained the general solution: Using our seed values, we obtain the system: Using the seed values allowed us to find the C and D specific to the sequence, i.e., to ensure the initial values are met. 
December 17th, 2010, 11:43 PM  #5 
Newbie Joined: Dec 2010 Posts: 11 Thanks: 0  Re: Recurrence relation
For instance, we have a sequence like this: 3, 8, 22, 60, 164... The recurrence relation is: Rn = 2(Rn1 + Rn2) Do we obtain the seed value R0 by this? R2 = 2R1 + 2R0 2R0 = 8  2*3 R0 = 1 
December 17th, 2010, 11:49 PM  #6 
Senior Member Joined: Jul 2010 From: St. Augustine, FL., U.S.A.'s oldest city Posts: 12,211 Thanks: 520 Math Focus: Calculus/ODEs  Re: Recurrence relation
Yes you could do that to get: or simply use the given values: Either way, you will get the same closed form for the sequence (with different values for C and D). However, I recommend using the given values so that for n = 0. 
December 17th, 2010, 11:57 PM  #7 
Newbie Joined: Dec 2010 Posts: 11 Thanks: 0  Re: Recurrence relation
I see. Thank you very much!


Tags 
recurrence, relation 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Recurrence relation  Joselynn  Real Analysis  2  September 14th, 2013 12:52 AM 
Recurrence relation  Dragonkiller  Linear Algebra  2  May 15th, 2012 10:49 AM 
recurrence relation fn+4  fe phi fo  Applied Math  3  December 4th, 2011 09:22 AM 
recurrence relation  tuzzii  Real Analysis  1  October 6th, 2007 10:25 AM 
Recurrence Relation  roguebyte  Advanced Statistics  1  December 31st, 1969 04:00 PM 