GAP Manual: 46.22. Lucas

Lucas( P, Q, k )

Lucas 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 alpha, beta be the two roots of x^2 - P x + Q then we define
Lucas( P, Q, k )[1] = U_k = (alpha^k - beta^k) / (alpha- beta) and
Lucas( P, Q, k )[2] = V_k = (alpha^k + beta^k) and as a convenience
Lucas( P, Q, k )[3] = Q^k.

The following recurrence relations are easily derived from the definition
U_0 = 0, U_1 = 1, U_k = P U_(k-1) - Q U_(k-2) and
V_0 = 2, V_1 = P, V_k = P V_(k-1) - Q V_(k-2).
Those relations are actually used to define Lucas if alpha= beta.

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 - 2 Q^k, V_(2k+1) = ((P^2-4Q) U_(2k) + P V_(2k)) / 2.

Fibonnaci(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