So I was bored in class one day and decided to play around with the famous fibonacci sequence. So I started to play with it's definition:
Fn = Fn-1 + Fn-2
From there I started to derive other solutions as it is a recursive function that have each replaced by using this definition and playing with the subscripts:
Fn = (Fn-2 + Fn-3) + Fn-2
Fn = 2(Fn-2) + Fn-3
Fn = 2(Fn-3 + Fn-4) + Fn-3
Fn = 3(Fn-3) + 2(Fn-4)
.... doing the same expansion of the first
Fn = 5(Fn-4) + 3(Fn-5)
Fn = 8(Fn-5) + 5(Fn-6)
Fn = 13(Fn-6) + 8(Fn-7)
Fn = 21(Fn-7) + 13(Fn-6)
See the pattern? Look at the coefficients of the equations, they are adding themselves up sequentially and are all fibonacci numbers Here is the general form: For an integer x which is the index within the fibonacci sequence
Fn = Fx+1(Fn-x) + Fx(Fn-x-1)
It allows computation of fibonacci numbers using an algorithm which is log(n) complexity rather than n2 or n complexity.
Here is the function in javascript
function f(n){
if( num == 0 || num == 1 || num == 2){
return 1
}
const x=parseInt(n/2,10)
return (f(x+1)*f(n-x)) + (f(x)*f(n-x-1))
}