
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 22nd, 2009, 03:55 PM  #1 
Newbie Joined: Feb 2008 Posts: 11 Thanks: 0  Find non recursive formula for the fibonacci sequence
Hey there guys, I have a question in my assignment that asks to find a non recursive formula for the fibonacci sequence. Im pretty much going to bail on the question as I have no idea even where start. I know the non recursive formula however I have no idea how to arrive at the result using characteristic equations. The book we are using is pretty confusing as it really does not show a step by step example so I really can't grasp the concepts. The book we are using is Discrete Mathematics for Computing by Peter Grossman I was wondering if anyone knows how to solve this type of question or can put me on the right track as how to even attempt this question, or does anyone know of any resources that I could use to help me. Any information would be great !! Cheers Trev 
May 22nd, 2009, 04:42 PM  #2 
Senior Member Joined: May 2008 From: York, UK Posts: 1,300 Thanks: 0  Re: Find non recursive formula for the fibonacci sequence
The Fibonacci numbers satisfy Therefore we can show that and so by diagonalising the matrix you can find the nonrecursive formula. 
May 22nd, 2009, 05:03 PM  #3 
Newbie Joined: Feb 2008 Posts: 11 Thanks: 0  Re: Find non recursive formula for the fibonacci sequence
We have not been taught how to solve linear recurrences using matrices, so I probably should not use that method. We are to solve it by working out the characteristic equation first which I am not sure how to do, then solve the fibonacci sequence from there. Thanks for the help anyway ! Trev 
May 22nd, 2009, 09:08 PM  #4 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Find non recursive formula for the fibonacci sequence
In the end you'll just have two exponential terms added or subtracted together. It's easy enough to find the first (large) term  just find the expected ratio between numbers. You can then solve for the second term with small numbers, then prove that the recurrence relation holds.

May 29th, 2009, 02:16 PM  #5 
Newbie Joined: Jul 2008 Posts: 7 Thanks: 0  Re: Find non recursive formula for the fibonacci sequence
Do you want Binet's formula? F(n) = ( g^n  (1g)^n) / sqrt(5) where g = (1 + sqrt(5))/2 ? That's not recursive. 
May 29th, 2009, 08:58 PM  #6 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Find non recursive formula for the fibonacci sequence
I assumed that's what was desired.


Tags 
fibonacci, find, formula, recursive, sequence 
Search tags for this page 
fibonacci sequence, any equation/formula involved,how to find fibonacci sequence using phi recursion formula,non recursive equations,NUMBER THEORY FIBONACCI NUMBERS IN PDF,non recursive fibonacci formula
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fibonacci Sequence  aaronmath  Calculus  2  December 6th, 2011 07:57 AM 
formula remains true Fibonacci sequence  fe phi fo  Applied Math  1  December 4th, 2011 03:04 PM 
RECURSIVE SEQUENCE  milagros  Real Analysis  0  October 26th, 2011 11:46 AM 
Fibonacci Sequence  BobDole2000  Algebra  2  August 4th, 2008 11:18 PM 
Find the Formula for a Sequence 200, 500, 900, 1400, 1910  Sheelby  Algebra  0  March 3rd, 2008 02:25 PM 