Lucas numbers

Lucas numbers
Original: The Nth User at English Wikipedia Vector: Begoon · CC BY-SA 4.0 · source
Name	Lucas numbers
First discovered	Édouard Lucas
Field	Number theory
Related	Fibonacci numbers, Perrin sequence, Lucas sequences

Lucas numbers are an integer sequence closely related to the Fibonacci number sequence, defined by a simple linear recurrence with fixed initial values. They appear across mathematics in combinatorics, algebraic identities, matrix theory, and Diophantine problems, and have historical connections to 19th-century recreational mathematics and to work by Édouard Lucas, Leonhard Euler, and later investigators in algebraic number theory. The sequence is notable for sharing spectral, algebraic, and asymptotic properties with other second-order linear recurrences such as the Pell equation sequences and certain Lucas sequences studied by Ferdinand von Lindemann and contemporaries.

Definition and sequence

The sequence is defined by the recurrence relation L_n = L_{n-1} + L_{n-2} for n ≥ 2 with initial values L_0 = 2 and L_1 = 1. Its first terms are 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, ... which are frequently tabulated alongside the Fibonacci number sequence in classical references and numerical compendia. The recurrence and initial conditions connect the sequence to families of linear recurrences treated in the work of Augustin-Louis Cauchy and Carl Friedrich Gauss on linear difference equations.

Properties and identities

Lucas numbers satisfy many identities paralleling those for Fibonacci numbers. They obey L_{m+n} = L_m F_{n+1} + L_{m-1} F_n and L_{n}^2 - 5F_{n}^2 = 4(-1)^n, revealing a quadratic Diophantine relation linked to the Pell equation. Other algebraic identities include L_{2n} = L_n^2 - 2(-1)^n and the Cassini-like formula F_{n+1}F_{n-1} - F_n^2 = (-1)^n with analogues replacing Fibonacci entries by Lucas entries. Multiplicative and addition formulas relate to work on integer sequences by D. H. Lehmer and to recurrence classification in the style of Édouard Lucas's theory of Lucas sequences. Periodicity modulo m (Pisano periods for Fibonacci) has an analogue for Lucas sequences studied in contexts involving Évariste Galois-type field automorphisms and modular arithmetic.

Relationship to Fibonacci numbers

The Lucas sequence is intimately connected to the Fibonacci sequence by linear combinations: L_n = F_{n-1} + F_{n+1}, and also L_n = F_n + 2F_{n-1} for n ≥ 1. Both sequences share the same characteristic polynomial x^2 − x − 1, so they have common eigenvalues φ = (1+√5)/2 and 1−φ = (1−√5)/2, linking them to algebraic integers studied by Richard Dedekind and ideals in quadratic fields such as Q(√5). Many congruence properties and primality tests (e.g., tests for Lucas probable primes) exploit this relationship and were developed further by researchers like Samuel Wagstaff and Hugh C. Williams in computational number theory.

Binet formula and closed form

A closed-form expression analogous to the Binet formula for Fibonacci numbers expresses L_n as L_n = φ^n + (1−φ)^n, where φ = (1 + √5)/2. This form arises from solving the characteristic equation x^2 − x − 1 = 0 and is used in asymptotic estimates: L_n ~ φ^n, with exponential growth governed by φ. The algebraic nature of φ connects the closed form to studies by Kummer and Kronecker on values of algebraic numbers, and enables derivation of identities, irrationality measures, and linear forms in logarithms treated in transcendence theory by Alan Baker.

Combinatorial and number-theoretic interpretations

Combinatorially, Lucas numbers count certain tilings and compositions closely related to those counted by Fibonacci numbers: they enumerate circular tilings of an n-bead necklace by tiles of lengths 1 and 2 (with orientation distinctions), paralleling problems in enumerative combinatorics discussed by George Pólya and Harary in graph enumeration contexts. Number-theoretically, Lucas numbers arise in divisibility sequences: gcd(L_m, L_n) = L_{gcd(m,n)}, mirroring properties of Fibonacci numbers and fitting into the theory of divisibility sequences explored by Ward and Morgan Ward. Prime-divisor distribution in Lucas numbers connects to work on primitive divisors and Zsigmondy-type results by Zsigmondy and later refinements by Bilu and collaborators.

Matrix and generating function representations

The sequence can be generated by powers of the companion matrix 1 1; 1 0: specifically, the n-th power yields entries that are Fibonacci numbers while a related linear combination produces L_n; matrix methods link to linear algebra treatments by Jordan and to spectral analysis in operator theory considered by John von Neumann. The ordinary generating function for L_n is G(x) = (2 − x)/(1 − x − x^2), a rational function that situates Lucas numbers in the context of rational formal power series and automata studied by N. J. Fine and analytic combinatorics techniques associated with Philippe Flajolet.

Applications and occurrences in nature and computation

Lucas numbers appear in algorithmic analysis, pseudorandom number generation, and cryptographic primality tests that adapt Lucas sequences for probable-prime certificates used in practical systems evaluated by researchers such as Carl Pomerance and Miller–Rabin-style investigations. They surface in modeling phyllotaxis and growth patterns in botany alongside Fibonacci models cited in the literature on Heliotropism and in design problems in architecture referenced by proponents of classical proportion such as Le Corbusier. In physics and engineering, Lucas-type recurrences arise in discretized dynamical systems and continued fraction expansions studied by John Wallis and modern numerical analysts. Their ubiquity stems from the shared algebraic skeleton with the Fibonacci sequence and the ubiquity of the characteristic polynomial x^2 − x − 1 in second-order linear systems.

Category:Integer sequences