mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-11-24, 01:02   #1
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

24×32×5 Posts
Default Fibonacci Formula

Hi all,

I thought I would tell about a little known Fibonacci formula that I found, and then later found it in the literature. A deffinition of Fibonacci numbers is -
F(n) = F(n-1) + F(n-2) with F(0) = F(1) = 1
This is a formula that lets you compute F(2n), knowing F(n) and F(n-1).
The most general form is -

F(n) = F(k)*F(n-k) + F(k-1)*F(n-k-1)

substituting n=2k or n=2k+1 gives interesting results.
I will try to link to my derivation

https://docs.google.com/viewer?a=v&p...AwMGIzOTU5NjRk

Regards,
Matt
Attached Files
File Type: pdf Another Fibonacci Equation.pdf (226.1 KB, 148 views)
MattcAnderson is offline   Reply With Quote
Old 2012-11-24, 01:18   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Take a look at the bottom of this section, and this section. The fourth formula of the latter seems to contradict one of your special cases, and it also has a general formula for Fkn+c.

Though your formula doesn't appear, I'd guess that someone's probably thought of it before given it's rather simple derivation.
Dubslow is offline   Reply With Quote
Old 2012-11-24, 03:23   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×17×139 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
F(0) = F(1) = 1
I believe that you "destroy" a lot of mathematical (and also biological ) things with this unintentional shift...
For example you can not say anymore that "the only fibo numbers that can be prime are those with a prime index".... and many other such affirmations...
LaurV is offline   Reply With Quote
Old 2012-11-24, 10:17   #4
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

2D016 Posts
Default

Hi,

Thanks for the replies. You are right, the standard definition of Fibonacci numbers includes F(1) = F(2) = 1. Mentioning that F(0) = 1 was an error.

With this change, the formulas currently at the bottom of the Wikipedia article sections cited are exactly the same ones I mentioned.

-Matt
MattcAnderson is offline   Reply With Quote
Old 2012-11-24, 23:28   #5
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

65110 Posts
Smile Exact formula.

Here's a formula for the Fibonacci numbers. It even works for negative indices:

Fn=(phin-(-phi)-n)/sqrt(5),

where phi is the Golden Ratio: (sqrt(5)+1)/2.
Stargate38 is offline   Reply With Quote
Old 2013-01-08, 20:05   #6
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

24×32×5 Posts
Default

I corrected my derivation. This formula is useful because a person can calculate large Fibonacci numbers F(n) with integer arithmatic and fewer steps than the definition equation. For example, if someone wants to calculate F(100), Start with F(1), F(2), and F(3) then find F(6), F(12), F(24), F(25), F(50), and finally F(100). This is shorter than iterating 100 times.
Attached Files
File Type: pdf Fibonacci Equation.pdf (156.5 KB, 128 views)
MattcAnderson is offline   Reply With Quote
Old 2013-01-11, 13:12   #7
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

23×73 Posts
Default

Hendrik Lenstra wrote a magazine article about profinite Fibonacci numbers:
http://www.math.leidenuniv.nl/~hwl/papers/fibo.pdf

With profinite integers, you get 8 extra fixed points.
Nick is offline   Reply With Quote
Old 2013-01-14, 23:29   #8
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

3×7×31 Posts
Default

There is also a formula that uses the Lucas numbers:

Fn*Ln=F2n :)
Stargate38 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fibonacci like sequences MattcAnderson Miscellaneous Math 1 2017-08-24 16:22
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
Odd Fibonacci pseudoprimes efeuvete Math 7 2013-05-26 11:24
Fibonacci modulo Fibonacci robert44444uk Math 3 2007-05-19 07:15
Fibonacci sums? TTn Math 2 2002-10-25 21:47

All times are UTC. The time now is 12:47.

Mon May 17 12:47:12 UTC 2021 up 39 days, 7:28, 0 users, load averages: 1.43, 1.61, 1.66

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.