All Forums
 Homework Help
the fibonacci sequence--is there an equation?

 Printer Friendly
 
Author Previous Topic Topic Next Topic  
brum
Radio Wave


USA
14 Posts
Posted - 02/27/2003 :  01:49:23  Show Profile Send a private Message  Send brum an instant message
is there an equation for the fibonacci sequence

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987


(note: some list "0" as the first term others start with the "1" as the first term)


i.e. im looking for an equation where i punch in the term number (n) and it spits out the value (i.e. i input "7" for n and it gives me 13)

tn = n(n+1)/2

(^this is obviously NOT the right equation)


im not entirely sure if one exists, i heard there is one that involves cosines and stuff, but im thinking there just isn't an equation for it without using Loops in a computer program to find out the value

thanks in advance for the help



Alert Mentor now

vanwinkel
Radio Wave


USA
21 Posts
Posted - 02/27/2003 :  04:18:27  Show Profile  Send a private Message
fn = (1/5)((1+5)/2)n - (1/5)((1-5)/2)n



Alert Mentor now Go to Top of Page

AdeofinxCorp
Radio Wave


Canada
44 Posts
Posted - 02/28/2003 :  04:04:02  Show Profile  Send a private Message  Send AdeofinxCorp an ICQ Message
How did you find that equation?



Alert Mentor now Go to Top of Page

OH man
Radio Wave


USA
86 Posts
Posted - 02/28/2003 :  15:38:22  Show Profile  Send a private Message  Visit OH man's Homepage  Send OH man an ICQ Message  Send OH man an instant message
I tried that one..didnt work. Maybe I typed it in wrong, or you wrote it wrong


=============
This space intentionally left blank.
Dave "dav2008" Groysman


Alert Mentor now Go to Top of Page

HallsofIvy
Micro Wave


USA
163 Posts
Posted - 02/28/2003 :  17:41:23  Show Profile  Send a private Message
You need a little experience with "recursive" equations to get started:

Recursive equations tend to lead to power functions as solutions so a good way to approach almost any such equation is:
Look for a solution of the form fn= axn.

The fibonacci numbers satisfy fn + 2= fn + 1 + fn or a xn + 2= axn + 1 + axn. We can divide by a and rewrite as xn + 2 - xn+1 - xn= 0. x= 0 will satisfy the recursive equation but not the initial requirements that f0= f1= 1 so we can divide through by x to get x2- x- 1= 0. There are, of course, two roots to that equation: x= (1+5)/2 and x= (1-5)/2.

As is usual with such linear problems, the general solution is a linear combination of these: fn= A((1+5)/2)n+ B((1-5)/2)n.

Solve for A and B so that f0= f1= 1.



Alert Mentor now Go to Top of Page

vanwinkel
Radio Wave


USA
21 Posts
Posted - 03/01/2003 :  04:01:03  Show Profile  Send a private Message
The formula I posted is correct. Please be sure you enter your parentheses EXACTLY as I did.

Note that this formula gives the sequence as F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, etc... Replace both n's in the formula with the term number, and it will give you the corresponding value.

"How it is done" is much too involved to post here. If you want to learn how to find explicit formulas for sequences like the fibonacci numbers, the topic to look up is "solving linear homogeneous recurrence relations with constant coefficients". This is normally covered in courses on discrete mathematics. Here are urls for a couple of sites that seem to cover this topic fairly well:

http://people.uncw.edu/tompkinsj/133/recursion/homogeneous.htm
http://www.cs.princeton.edu/courses/archive/fall02/cs341/lec9-10.pdf



Alert Mentor now Go to Top of Page

OH man
Radio Wave


USA
86 Posts
Posted - 03/01/2003 :  04:09:53  Show Profile  Send a private Message  Visit OH man's Homepage  Send OH man an ICQ Message  Send OH man an instant message
Yea, my bad, I typed it in wrong...

I thought the "/" was one big square root symbol, instead of divided by the square root


=============
This space intentionally left blank.
Dave "dav2008" Groysman


Alert Mentor now Go to Top of Page

jeff
Radio Wave


New Zealand
65 Posts
Posted - 03/01/2003 :  07:34:44  Show Profile  Send a private Message
Just out of curiosity, what's the relationship between the fibonacci sequence and the golden ratio???

ie fn=(1/5)(n - 1/n)

Jeff Lee

Alert Mentor now Go to Top of Page


Edited by - jeff on 03/01/2003 07:35:56
   

 Printer Friendly

 
load time: 1.6396