Applied Math Applied Math Forum

 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^2-At-B=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: 521 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: 521 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(Rn-1 + Rn-2) 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: 521 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post Joselynn Real Analysis 2 September 14th, 2013 12:52 AM Dragonkiller Linear Algebra 2 May 15th, 2012 10:49 AM fe phi fo Applied Math 3 December 4th, 2011 09:22 AM tuzzi-i Real Analysis 1 October 6th, 2007 10:25 AM roguebyte Advanced Statistics 1 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      