The Lucas numbers are the integers defined by , , and the recurrence relation
They obey the same recurrence as the Fibonacci numbers but have different initial values. Named after the French mathematician Édouard Lucas, they connect recurrence relations, the golden ratio, combinatorial counting, and divisibility properties. They are a particular instance of the broader family of Lucas sequences.
Definition and initial terms
Beginning with index zero, the sequence is
Each term after the first two is the sum of its predecessors. Some presentations begin with and , omitting ; including makes many identities valid without exceptions at zero.
The recurrence also extends the sequence uniquely to negative indices. Solving backward gives
Thus , , and .
Lucas numbers should not be confused with the separate sequence used in the Lucas–Lehmer test for Mersenne primes, although that test is also connected with the wider theory of Lucas sequences.
Closed form and growth
Let
Here is the golden ratio, and . The Lucas numbers have the closed form
To derive it, a trial solution to the recurrence leads to the quadratic equation
Its roots are and , so every solution has the form . The Lucas initial values give .
Because ,
More precisely,
Consequently, for every , is the nearest integer to . The closed form also explains why the generally irrational quantities and have an integer sum: their irrational parts cancel.
Relations with Fibonacci numbers
Write the Fibonacci initial values as and . Then
or equivalently,
These formulas show that Lucas numbers can be calculated directly from neighboring Fibonacci numbers.
Two important identities are
and
The latter places Fibonacci–Lucas pairs on the Diophantine equations
according to the parity of . It follows immediately from
Useful addition and doubling formulas include
and
A Lucas analogue of Cassini’s identity is
The finite sum of the sequence also has a simple form:
These identities can be established from the closed forms, the recurrence, or mathematical induction.
Generating function and matrix representation
The ordinary generating function is
Indeed, multiplying the series by cancels all coefficients of degree two and higher through the recurrence. The equality holds as a formal power series and analytically for .
A matrix representation uses
For ,
Taking the trace gives
which also holds at .
The eigenvalues of are and , providing another explanation of the closed form. This representation connects Lucas identities with matrix multiplication and supports efficient computation by repeated squaring.
Combinatorial interpretations
Lucas numbers count several kinds of objects in combinatorics, particularly arrangements with circular rather than linear boundary conditions.
For , is the number of subsets of the vertices of a cycle with labeled vertices that contain no adjacent pair. The empty subset is included.
To see this, fix one vertex and split the choices into two cases:
- If the vertex is excluded, the remaining choices form a path on vertices, giving possibilities.
- If it is included, both neighboring vertices must be excluded, leaving a path on vertices and giving possibilities.
The total is therefore
Equivalently, counts binary strings of length with no consecutive ones when the first and last positions are also treated as adjacent. Positions remain labeled: strings related by rotation are counted separately.
Counting these subsets by their size yields
where is a binomial coefficient. For cycle graphs with , the summand counts the allowed subsets containing exactly vertices.
Divisibility and prime terms
Lucas numbers exhibit many regularities in number theory. Their parity repeats with period three:
This follows by applying the recurrence modulo .
More generally, the sequence is purely periodic modulo every positive integer . In modular arithmetic, the update
is invertible, and there are only finitely many residue pairs.
For and odd positive ,
Unlike Fibonacci numbers, Lucas numbers do not satisfy for every positive : for example, does not divide .
A Lucas prime is a Lucas number that is a prime number. Early examples are
It is not known whether infinitely many Lucas primes exist.
For every prime ,
This congruence resembles Fermat’s little theorem, but its converse is false. Composite integers can satisfy , so this congruence alone does not establish primality.
Generalized Lucas sequences
The standard Lucas numbers belong to a two-parameter family. For fixed integers , define
and
The standard Fibonacci and Lucas numbers arise from
If are distinct roots of , then
This broader framework underlies many divisibility results and Lucas-based primality tests. The unqualified term “Lucas numbers” normally denotes the particular sequence , rather than every member of this family.
Computation
Sequential use of the recurrence computes with integer additions and storage for only two consecutive terms. Matrix exponentiation or Fibonacci fast-doubling identities reduce the number of arithmetic operations to , in big-O notation.
These operation counts do not make exact computation logarithmic in bit complexity: itself has a number of binary digits proportional to , and arithmetic on larger integers costs more. Direct evaluation of using fixed-precision floating-point arithmetic can lose enough accuracy to produce an incorrect rounded integer. Exact recurrence or doubling methods avoid that problem.