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