My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
kec11494 is offline  
 
December 17th, 2010, 10:40 PM   #2
Senior Member
 
MarkFL's Avatar
 
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
MarkFL is offline  
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?
kec11494 is offline  
December 17th, 2010, 10:55 PM   #4
Senior Member
 
MarkFL's Avatar
 
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.
MarkFL is offline  
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
kec11494 is offline  
December 17th, 2010, 11:49 PM   #6
Senior Member
 
MarkFL's Avatar
 
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.
MarkFL is offline  
December 17th, 2010, 11:57 PM   #7
Newbie
 
Joined: Dec 2010

Posts: 11
Thanks: 0

Re: Recurrence relation

I see. Thank you very much!
kec11494 is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 tuzzi-i Real Analysis 1 October 6th, 2007 10:25 AM
Recurrence Relation roguebyte Advanced Statistics 1 December 31st, 1969 04:00 PM





Copyright © 2019 My Math Forum. All rights reserved.