My Math Forum Recurrence relation

 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: $F_{n}=F_{n-1}+F_{n-2}$ with seed values $F_0=0$ and $F_1=1$. If we assume a solution of the form $F_n=r^n$ and substitute into the recursion formula, we have: $r^n=r^{n-1}+r^{n-2}$ Dividing through by $r^{n-2}$. we have: $r^2=r+1$ yielding the characteristic equation: $r^2-r-1=0$ whose roots are $r=\frac{1\pm\sqrt{5}}{2}$ Since these roots are distinct, we have the general solution: $F_n=C\left(\frac{1+\sqrt{5}}{2}\right)^n+D\left(\f rac{1-\sqrt{5}}{2}\right)^n$ Using our seed values, we obtain the system:  $1=C\left(\frac{1+\sqrt{5}}{2}\right)+D\left(\frac{ 1-\sqrt{5}}{2}\right)$ Solving, we find: $C=\frac{1}{\sqrt{5}}$ and $D=-\frac{1}{\sqrt{5}}$ thus we have: $F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5} }{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$ 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: $F_n=C\left(\frac{1+\sqrt{5}}{2}\right)^n+D\left(\f rac{1-\sqrt{5}}{2}\right)^n$ Using our seed values, we obtain the system: $F_0=0=C\left(\frac{1+\sqrt{5}}{2}\right)^0+D\left( \frac{1-\sqrt{5}}{2}\right)^0=C+D$ $F_1=1=C\left(\frac{1+\sqrt{5}}{2}\right)^1+D\left( \frac{1-\sqrt{5}}{2}\right)^1=C\left(\frac{1+\sqrt{5}}{2}\ right)+D\left(\frac{1-\sqrt{5}}{2}\right)$ 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: $R_0=1$ $R_1=3$ or simply use the given values: $R_0=3$ $R_1=8$ 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 $R_0=3$ 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 Linear 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