My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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
Airmax is offline  
 
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 non-recursive formula.
mattpi is offline  
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
Airmax is offline  
May 22nd, 2009, 09:08 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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 - (1-g)^n) / sqrt(5) where g = (1 + sqrt(5))/2 ?

That's not recursive.
cornwall_5 is offline  
May 29th, 2009, 08:58 PM   #6
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
fibonacci, find, formula, recursive, sequence



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fibonacci Sequence aaron-math 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





Copyright © 2019 My Math Forum. All rights reserved.