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
GAP 3.4.4