46.20 Fibonacci

Fibonacci( n )

Fibonacci returns the nth number of the Fibonacci sequence. The Fibonacci sequence F_n is defined by the initial conditions F_1=F_2=1 and the recurrence relation F_{n+2} = F_{n+1} + F_{n}. For negative n we define F_n = (-1)^{n+1} F_{-n}, which is consistent with the recurrence relation.

Using generating functions one can prove that F_n = phi^n - 1/phi^n, where phi is (sqrt{5} + 1)/2, i.e., one root of x^2 - x - 1 = 0. Fibonacci numbers have the property Gcd( F_m, F_n ) = F_{Gcd(m,n)}. But a pair of Fibonacci numbers requires more division steps in Euclid's algorithm (see Gcd) than any other pair of integers of the same size. Fibonnaci(k) is the special case Lucas(1,-1,k)[1] (see Lucas).

    gap> Fibonacci( 10 );
    55
    gap> Fibonacci( 35 );
    9227465
    gap> Fibonacci( -10 );
    -55 

Previous Up Top Next
Index

GAP 3.4.4
April 1997