17.3 Fibonacci and Lucas Sequences

returns the nth number of the Fibonacci sequence. The Fibonacci sequence F_n is defined by the initial conditions F₁ = F₂ = 1 and the recurrence relation F_n+2 = F_n+1 + F_n. For negative n we define F_n = (-1)ⁿ⁺¹ F_-n, which is consistent with the recurrence relation.

Using generating functions one can prove that F_n = fⁿ - 1/fⁿ, where f is (Ö5 + 1)/2, i.e., one root of x² - 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 

returns the k-th values of the Lucas sequence with parameters P and Q, which must be integers, as a list of three integers.

Let a, b be the two roots of x² - P x + Q then we define Lucas( P, Q, k )[1] = U_k = (a^k - b^k) / (a- b) and Lucas( P, Q, k )[2] = V_k = (a^k + b^k) and as a convenience Lucas( P, Q, k )[3] = Q^k.

The following recurrence relations are easily derived from the definition U₀ = 0, U₁ = 1, U_k = P U_k-1 - Q U_k-2 and V₀ = 2, V₁ = P, V_k = P V_k-1 - Q V_k-2. Those relations are actually used to define Lucas if a = b.

Also the more complex relations used in Lucas can be easily derived U_2k = U_k V_k, U_2k+1 = (P U_2k + V_2k) / 2 and V_2k = V_k² - 2 Q^k, V_2k+1 = ((P²-4Q) U_2k + P V_2k) / 2.

Fibonacci(k) (see Fibonacci) is simply Lucas(1,-1,k)[1]. In an abuse of notation, the sequence Lucas(1,-1,k)[2] is sometimes called the Lucas sequence.

gap> List( [0..10], i->Lucas(1,-2,i)[1] );
[ 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341 ]      # 2^k - (-1)^k)/3
gap> List( [0..10], i->Lucas(1,-2,i)[2] );
[ 2, 1, 5, 7, 17, 31, 65, 127, 257, 511, 1025 ]  # 2^k + (-1)^k
gap> List( [0..10], i->Lucas(1,-1,i)[1] );
[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]          # Fibonacci sequence
gap> List( [0..10], i->Lucas(2,1,i)[1] );
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]             # the roots are equal 

[Top] [Previous] [Up] [Next] [Index]