In mathematics, the Lucas sequences
are certain constant-recursive integer sequences that satisfy the recurrence relation where
Any sequence satisfying this recurrence relation can be represented as a linear combination of the Lucas sequences
More generally, Lucas sequences
represent sequences of polynomials in
Lucas sequences are named after the French mathematician Édouard Lucas.
, the Lucas sequences of the first kind
are defined by the recurrence relations: and It is not hard to show that for
, The above relations can be stated in matrix form as follows:
Initial terms of Lucas sequences
are given in the table: The characteristic equation of the recurrence relation for Lucas sequences
and the roots: Thus: Note that the sequence
also satisfy the recurrence relation.
, a and b are distinct and one quickly verifies that It follows that the terms of Lucas sequences can be expressed in terms of a and b as follows The case
In this case one easily finds that The ordinary generating functions are When
satisfy certain Pell equations: The terms of Lucas sequences satisfy relations that are generalizations of those between Fibonacci numbers
Another consequence is an analog of exponentiation by squaring that allows fast computation of
is a strong divisibility sequence.
Other divisibility properties are as follows:[1] The last fact generalizes Fermat's little theorem.
These facts are used in the Lucas–Lehmer primality test.
Like Fermat's little theorem, the converse of the last fact holds often, but not always; there exist composite numbers n relatively prime to D and dividing
Such composite numbers are called Lucas pseudoprimes.
A prime factor of a term in a Lucas sequence which does not divide any earlier term in the sequence is called primitive.
Carmichael's theorem states that all but finitely many of the terms in a Lucas sequence have a primitive prime factor.
[2] Indeed, Carmichael (1913) showed that if D is positive and n is not 1, 2 or 6, then
has a primitive prime factor.
In the case D is negative, a deep result of Bilu, Hanrot, Voutier and Mignotte[3] shows that if n > 30, then
has a primitive prime factor and determines all cases
has no primitive prime factor.
The Lucas sequences for some values of P and Q have specific names: Some Lucas sequences have entries in the On-Line Encyclopedia of Integer Sequences: Sagemath implements