Factoring Fibonacci

Im pretty sure this is original, just not very significant

Note: this is subscipt math when directly following 'F'

Factoring Fibonacci :

Slank
June 6, 2002

Note: subscipts are as follows: F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, F5 = 8, ... etc.


Fn = Fn-1 + Fn-2
Fn-1 = Fn-2 + Fn-3
Fn = ( Fn-2 + Fn-3) + Fn-2
Fn = 2Fn-2 + Fn-3

Fn = 3 Fn-3 + 2 Fn-4
Fn = (F3) Fn-3 + (F3-1) Fn-3-1

Fn = 5 Fn-4 + 3 Fn-5
Fn = (F4) Fn-4 + (F4-1) Fn-4-1

Fn = 8 Fn-5 + 5 Fn-5-1
Fn = (F5) Fn-5 + (F5-1) Fn-5-1

Fn = (Fk) Fn-k + (Fk-1) Fn-k-1

If n is even and greater than 1 we can choose k such that n=2k
which gives

Fn = (Fk) Fk + (Fk-1) Fk-1 = (Fk)� + (Fk-1)�

Fn = (Fk)� + (Fk-1)�

for n even :
Fn = (Fn/2)� + (F(n-2)/2)�


If n is odd and greater than 1 we know by definition

Fn+1 = Fn + Fn-1
Fn+1 - Fn-1 = Fn

Fn = Fn+1 - Fn-1
We know that n+1 & n-1 are both even, therefore from above

Fn+1 = (F(n+1)/2)� + (F(n+1-2)/2)�
Fn+1 = (F(n+1)/2)� + (F(n-1)/2)�
and
Fn-1 = (F(n-1)/2)� + (F(n-1-2)/2)�
Fn-1 = (F(n-1)/2)� + (F(n-3)/2)�
and because
Fn = Fn+1 - Fn-1
Fn = (F(n+1)/2)� + (F(n-1)/2)� - ((F(n-1)/2)� + (F(n-3)/2)�)
cancelling out like terms

for n odd :
Fn = (F(n+1)/2)� - (F(n-3)/2)�

therefore any term/element of the Fibonacci series such that n is an integer > 1 is either
a sum of a pair of squares of Fibonacci numbers
or the difference of a pair of squares of Fibonacci numbers
(If memory serves me, I think i did check n < 1; Fibonacci less than F0 ie F(-1), F(-2), etc calculated
using subtraction instead of addition. F1 = F0 + F(-1); F1-F0 = F(-1) )

Taking any Fibonacci number we can break it down into pairs of terms that are
approximately sequential values of the Fibonacci sequence ie.

F21
F21
(F11)� - (F9)�
( (F6)� - (F4)� )� - ( (F5)� - (F3)� )�
(((F3)� + (F2)�)� - ((F2)� + (F1)�)�)� - (((F3)� - (F1)�)� -((F2)� - (F0)�)�)�

calculate f0,f1,f2,f3 and plug them in

(((3)� + (2)�)� - ((2)� + (1)�)�)� - (((3)� - (1)�)� -((2)� - (1)�)�)�
((9 + 4)� - (4 + 1)�)� - ((9 - 1)� -(4 - 1)�)�
(13� - 5�)� - (8� -3�)�
(169 - 25)� - (64 -9)�
144�-55�
20736-3025
17711

F21=17711

plug in values square, add, subtract etc.

Note: with subscipts as follows: F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5, F5 = 8, ... etc. works equally well
but the subscript substitution is a little trickier and it inverts & alters
the odd & even subscript coorespondance

As a former computer science student it is recognisable that this allows for
an improved optimal algorithm from Big O of N (linear) to Log2(N)
.

Eemmm could you repeat that ??? PLease..mager?

[edit on 8-12-2004 by Horus_Re]

Now we know how to calculate the number of rabbits we started out with N months ago. Now isn't math fun?

I'm going to have to sit and think about that one. However, if it's a more efficient computing algorithmn, that in itself is a good deal. I'm not sure how they're computing Fibonacci these days.

I'm sorry, but I'm pretty sure that that formula has been derived before.

Although I can't find the derivation online, I do remember that I've had to derive that same formula as a problem for a lower division undergraduate computer science course several years ago. So it can't be original.

However, if you were born perhaps 100 years (or more?) ago, you'd have stumbled across something that I would think is significant.

(Like a quick way to approximate the golden ratio. )

Bravo.

[edit on 8-12-2004 by Nox]

slank:

try this:

f(n) = (1/(5^(1/2)))(((1 + 5^(1/2))/2)^(n+1) - (1 - (5^(1/2))/2)^(n+1))

(if you haven't seen that)

this website's probably the best "fibonacci fun" site on the web" www.mcs.surrey.ac.uk...

and there's also a math journal out there that's dedicated to results from the fibonacci numbers...I think it's the journal of fibonacci research

one more thing:

if your interest is in computation -- ie, with computers -- then your formulas (assuming they work, i haven't verified them but they look ok) are going to be faster in general. within a computer algebra system like mathematica, matlap, gap, pari, etc., numbers like (5^(1/2)) are handled symbolically and thus aren't a big issue (ie, they're no faster and no slower than other numbers in that computer algebra system) but in, say, c, you'd have to use floats to calculate fibonaccis with the direct formula, and that'd slow you down a bit...i don't think the little inaccuracies that pop up with floats would be enough to net you a wrong result until you got into n's in the range of several thousand or so, but that's an added risk as well.

for computational purposes, stick with integers.

.
It looks like Dijkstra did virtually the same thing.

F(2n-1) = F(n-1)� + F(n)�
F(2n) = ( 2 F(n-1) + F(n) ) F(n)

He got the exact same thing for F(2n-1), but used a slightly different method for F(2n), a square and an almost square.

My method comes up with a sum of squares for each case. (6 of one 1/2 dozen for the other)
The subscripts I have shown are shifted one from his. I have done it with his subscipting elsewhere, but you almost fall into it with the subscripting shown.

Oh Well, back to the drawing board.
.

.
Also if anyone is interested in seeing an easier to read version where the subscripting is apparent, I can email you a Word Pad document.
.

it's threads like these that leave me thinking ATS 4.0 (maybe 5.0 if 4.0's almost done) should have the following two things:

a) a wiki section
b) latex support (for math notation)

...anyways, if you're looking for more fibonacci, you can try any of the following:

i) generalized fibonacci (pick two starting numbers and go from there)
ii) generalized complex fibonacci (lots of ways to do this, usually it's pick two starting complex numbers, and let x_n+1 = i(x_n) + (x_n-1) or some other such)

or if you're more computer oriented, you can write a program to display ulam's prime number spiral and/or generalized fibonacci sequences...all of these are exercises where lots of neat results pop out without requiring heavy advanced math...

No, we're not talking about generating Fibonacci numbers, this is about factoring Fibonacci numbers. You know, what two Fibonacci numbers make up a given Fibonacci number. For instance if you have x number of rabbits (where x is a Fibonacci number) that multiply every day, how many rabbits did we have 9 days ago. Well we had y males and z females. We know this by factoring the end result number.

Originally posted by dbates
No, we're not talking about generating Fibonacci numbers, this is about factoring Fibonacci numbers. You know, what two Fibonacci numbers make up a given Fibonacci number. For instance if you have x number of rabbits (where x is a Fibonacci number) that multiply every day, how many rabbits did we have 9 days ago. Well we had y males and z females. We know this by factoring the end result number.

Um, I assumed that slank made a mistake when he said "factoring" Fibonnaci numbers because that can't really happen.

The average ratio between one number in the sequence with a previous number is the Golden Ratio, which is transcendent. It can't be factored due to this fact.

That's probably why we all just assumed he was talking about an approximation or algebraic calculation of Fibonnaci numbers.

.
'Factoring' was poetic licsence.

BTW this is not floating point math, it is pure interger math.
The subscripts are integers.
It will produce exact values.
no rounding errors etc.

It is reflective of all the inherent geometry of Fibonacci numbers.
F2 is folded and re-folded back into itself geometrically with each new fibonacci iteration.
.

slank:

your formula only makes use of integers. you were talking about using it as a way of calculating the nth fibonacci, which gave you one formula for evens and one for odds, but there's a generating formula (see my earlier post) that gives you the n'th fibonacci in a straightforward manner. the catch, though, is that it involves the difference of two non-integer terms -- (1 + 5^(1/2)/2 and (1-5^(1/2))/2 -- to the n+1th power, so if you were to use it to calculate fibonacci's on a computer you'd either have to be in a computer algebra system that can handle the roots symbolically or you'd have to use floating points to do your calculation.

Nox:

just to pick nits, phi the "golden mean" isn't transcendental, just algebraic. algebraic = expressible as a root of a finite-degree polynomial with integer coefficients (like square root of two is a root of x^2 -2), transcendental = not expressible as a root of a finite-degree polynomial with integer coefficients (e and pi are famous transcendentals).

Originally posted by sisonek
slank:

your formula only makes use of integers. you were talking about using it as a way of calculating the nth fibonacci, which gave you one formula for evens and one for odds, but there's a generating formula (see my earlier post) that gives you the n'th fibonacci in a straightforward manner. the catch, though, is that it involves the difference of two non-integer terms -- (1 + 5^(1/2)/2 and (1-5^(1/2))/2 -- to the n+1th power, so if you were to use it to calculate fibonacci's on a computer you'd either have to be in a computer algebra system that can handle the roots symbolically or you'd have to use floating points to do your calculation.

Nox:

just to pick nits, phi the "golden mean" isn't transcendental, just algebraic. algebraic = expressible as a root of a finite-degree polynomial with integer coefficients (like square root of two is a root of x^2 -2), transcendental = not expressible as a root of a finite-degree polynomial with integer coefficients (e and pi are famous transcendentals).

You're right. I meant to just say irrational, which would have suited my purpose anyway. Was too hasty because I just wanted to lump the golden ratio with pi and e because people are more familiar with those.

The next number is the sum of the two numbers previous.

I was reading "Five Equations the Changed the World" by Michael Guillen, Ph.D.

and he mentioned that Einstein was intrigued by how nature emulates

these numbers.

But it is bugging me out now. I saw a bug in the bathroom yesterday.

The day before had a bug. Today I got rid of two bugs.

Will tomorrow I see three bugs.

This has been done before, although what I believe you're attempting to do is trivial. If you ever take a course called Real Analysis (sometimes called Advanced Calculus) you will play with the Fibonacci sequence - mainly (at least I did this) to see how you can get the Golden Ratio out of it. You will do other things with them, though. Believe me, though, it is the hardest course you will ever have to take. I've taken many math courses...Calc 1-3, Diff Eq, Boundary Value Problems, Complex Variables etc etc and other applied mathematics, but Real Analysis was the beast of them all (although very interesting).

It made me know I didn't want to be a mathematician,