GAP Manual: 46.21. 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