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,

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,

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

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.

See also

Arithmetic sequence
Geometric sequence

---