Fibonacci sequence

This tools is related to Fibonacci sequence. It calculates :
- The sequence term of rank n.
- The sum of the first n terms.


Fibonacci Sequence

Fibonacci numbers form a sequence of positive integers in which each term is obtained by summing up the two preceding terms, the first two terms being equal to 0 and 1. The general term of Fibonacci's sequence is as follows,

`F_0 =0, F_1 =1`

`F_n = F_(n-1) + F_(n-2)` for `n >= 2`

Binet's Formula

Binet's formula is an explicit formula of the n-th term of the Fibonacci sequence. So, if `F_n` is the term of rank n then,

`F_n=1/sqrt(5)*(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)`

Another way to write this formula using the Golden ratio is as follows,

`phi = (1+sqrt(5))/2`

`F_n=1/sqrt(5)*(phi^n-(-phi)^-n)`

Fibonacci numbers algorithms

Simple algorithm


//This algorithm simply applies the definition of Fibonacci sequence
function fibonacci(n)
    if n = 0
        return 0

    if n = 1
        return 1
        
    return fibonacci(n-1) + fibonacci(n-2)

This algorithm is given for pedagogic purpose. It is not optimal and not recommended to use,
- it computes multiples times terms preceding n-th term.
- time execution is an exponential function of n.

Dynamic algorithm


function fibonacci(n)
    //initialization of fibonacci numbers list
    f = (0,1)

    For i from 2 to n
        add the following element to f list : f[i-1] + f[i-2]
    
    return f[n]

The main advantage of this algorithm is that it avoids re-calculating the term at each iteration as in the first algorithm.

Algorithm using Binet's formula


//this function calculates Fibonacci numbers using the golden ratio
fonction fibonacci(n)
    phi = (1+sqrt(5))/2
    return (phi^n-(-phi)^(-n))/sqrt(5)

This algorithm ist faster as it does not calculate preceding term of rank less than n. its disadvantage is that depending on the machine it is executed on, from a certain rank of n, it will reach a limit for the number of computed decimal places and then round the result to the wrong values.

The first 50 terms of the Fibonacci sequence

Notations :
n is a positive integer
`F_n`: the Fibonacci term of rank n
`S_n`: the sum of the first terms `F_0 + F_1 + ... + F_n`
`F_n/F_(n-1)`: the ratio of two consecutive terms. This is an approximation of the golden ratio when n tends to infinity.

Golden ratio : ` phi = (1+sqrt(5))/2 approx` 1.6180339887499
We notice from the following table that the ratio `F_n/F_(n-1)` rapidly converges towards the golden ratio.

n `F_n` `S_n` `F_n/F_(n-1)`
000
111
2121
3242
4371.5
55121.66666666666667
68201.6
713331.625
821541.61538461538462
934881.61904761904762
10551431.61764705882353
11892321.618181818182
121443761.61797752808989
132336091.618055555556
143779861.61802575107296
1561015961.61803713527851
1698725831.61803278688525
17159741801.61803444782168
18258467641.61803381340013
194181109451.61803405572755
206765177101.61803396316671
2110946286561.6180339985218
2217711463671.61803398501736
2328657750241.6180339901756
24463681213921.61803398820533
25750251964171.6180339889579
261213933178101.61803398867044
271964185142281.61803398878024
283178118320391.6180339887383
2951422913462681.61803398875432
3083204021783081.6180339887482
31134626935245771.61803398875054
32217830957028861.61803398874965
33352457892274641.61803398874999
345702887149303511.61803398874986
359227465241578161.61803398874991
3614930352390881681.61803398874989
3724157817632459851.6180339887499
38390881691023341541.61803398874989
39632459861655801401.6180339887499
401023341552679142951.61803398874989
411655801414334944361.6180339887499
422679142967014087321.6180339887499
4343349443711349031691.6180339887499
4470140873318363119021.6180339887499
45113490317029712150721.6180339887499
46183631190348075269751.6180339887499
47297121507377787420481.6180339887499
484807526976125862690241.6180339887499
497778742049203650110731.6180339887499
5012586269025329512800981.6180339887499

See also

Arithmetic sequence
Geometric sequence