Fact-checked by Grok 2 weeks ago

Lucas sequence

In mathematics, a Lucas sequence is an integer sequence \{u_n\} defined by the linear recurrence relation u_n = P u_{n-1} - Q u_{n-2} for n \geq 2, with initial conditions u_0 = 0 and u_1 = 1, where P and Q are fixed integer parameters.^[1]^[2] Named after the French mathematician Édouard Lucas (1842–1891), who introduced these sequences in his 1878 work Théorie des fonctions numériques simplement périodiques, they generalize the Fibonacci sequence and form a fundamental class of linear recurrence sequences in number theory.^[2] Associated with each Lucas sequence \{u_n(P, Q)\} is a companion sequence \{v_n(P, Q)\}, defined by the same recurrence but with initial conditions v_0 = 2 and v_1 = P.^[1]^[2] The roots of the characteristic equation x^2 - Px + Q = 0 are \alpha = \frac{P + \sqrt{D}}{2} and \beta = \frac{P - \sqrt{D}}{2}, where D = P^2 - 4Q is the discriminant, assuming D > 0.^[1] These yield closed-form Binet-like formulas: u_n = \frac{\alpha^n - \beta^n}{\alpha - \beta} and v_n = \alpha^n + \beta^n.^[2] Prominent examples include the Fibonacci sequence, given by u_n(1, -1), which starts 0, 1, 1, 2, 3, 5, 8, ... and its companion, the Lucas numbers v_n(1, -1), starting 2, 1, 3, 4, 7, 11, 18, ....^[1]^[2] Other instances are the Pell numbers u_n(2, -1), starting 0, 1, 2, 5, 12, 29, ..., and the Pell-Lucas numbers v_n(2, -1), starting 2, 2, 6, 14, 34, ....^[1] These sequences satisfy numerous identities, such as u_{2n} = u_n v_n and v_{2n} = v_n^2 - 2 Q^n, enabling efficient computation for large indices in logarithmic time.^[2] Lucas sequences exhibit rich divisibility properties, including Lucas's theorem: if \gcd(P, Q) = 1, then \gcd(u_m, u_n) = |u_{\gcd(m,n)}|.^[2] They play a key role in analytic number theory, Diophantine equations, and primality testing; for instance, the Lucas-Lehmer test uses a specific Lucas sequence to determine whether Mersenne numbers $2^p - 1 are prime.^[1] Their study extends to modular arithmetic and algebraic number fields, with ongoing research into ranks of appearance and primitive divisors.^[2]

Definition and Basics

Recurrence Relation

The Lucas sequence is defined by the second-order linear homogeneous recurrence relation with constant coefficients given by U_n = P U_{n-1} - Q U_{n-2} for n \geq 2, where P and Q are fixed integer parameters.^[3] This relation generates each term as a linear combination of the two preceding terms, scaled by the parameters P and Q.^[1] As a linear homogeneous recurrence of order 2, the sequence satisfies the associated characteristic equation r^2 - P r + Q = 0, whose roots determine the general solution form for the sequence.^[3] Solving this quadratic equation provides the basis for expressing U_n in closed form, typically as a linear combination of powers of the roots, though the explicit solution depends on the discriminant D = P^2 - 4Q.^[1] This general form extends the Fibonacci recurrence, which arises as a special case when the relation is rewritten to match the structure F_n = 1 \cdot F_{n-1} - (-1) F_{n-2}.^[3]

Initial Conditions and Parameters

The standard Lucas sequence, denoted as U_n(P, Q), is defined with the initial conditions U_0 = 0 and U_1 = 1, where P and Q are parameters that govern the recurrence.^[1] These initial values distinguish the Lucas sequence from its companion sequence V_n(P, Q), which starts with V_0 = 2 and V_1 = P.^[1] These specific initial conditions for U_n(P, Q) ensure a direct linear relation to the companion sequence, particularly in the case where P = 1 and Q = -1, corresponding to the Fibonacci numbers for U_n(1, -1). In this scenario, the companion V_n(1, -1) = L_n = F_{n-1} + F_{n+1}, where L_n are the classical Lucas numbers and F_n is the nth Fibonacci number with F_0 = 0 and F_1 = 1.^[4] This relation highlights the complementary nature of the sequences, as both satisfy the same recurrence but with initials that form a basis for the solution space of the linear homogeneous equation.^[1] The parameters P and Q are typically taken to be integers in number-theoretic applications, allowing the sequences to produce integer terms. The behavior of the roots of the characteristic equation x^2 - P x + Q = 0 is determined by the discriminant D = P^2 - 4Q: if D > 0, there are two distinct real roots; if D = 0, there is a repeated real root; and if D < 0, the roots are complex conjugates.^[1] While the standard form emphasizes U_n(P, Q) with the given initials, generalized Lucas sequences may employ different starting values for broader applications, though the conventional choice prevails in core studies due to its alignment with fundamental identities.^[1]

Examples

Relation to Fibonacci Sequence

The Lucas sequence with parameters P=1 and Q=-1 produces the Fibonacci numbers F_n, defined by F_0 = 0, F_1 = 1, and F_n = F_{n-1} + F_{n-2} for n \geq 2.^[4] Its companion sequence, the Lucas numbers L_n, shares the same recurrence relation L_n = L_{n-1} + L_{n-2} for n \geq 2, with initial conditions L_0 = 2 and L_1 = 1.^[4] This companion sequence serves as a natural counterpart to the Fibonacci sequence, highlighting their intertwined properties.^[4] A key explicit relation connects the two sequences: L_n = F_{n-1} + F_{n+1} for n \geq 1.^[4] For illustration, the first few Lucas numbers are L_0 = 2, L_1 = 1, L_2 = 3, L_3 = 4, L_4 = 7, L_5 = 11, which can be verified against the corresponding Fibonacci terms F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5.^[5] Basic identities further link the sequences, such as the generalization of Cassini's identity: L_n^2 - 5 F_n^2 = 4 (-1)^n.^[6] This relation underscores the structural similarity between the Lucas and Fibonacci numbers, extending classical properties of the latter to the former. The Lucas numbers were introduced in the 1870s by French mathematician Édouard Lucas (1842–1891), who studied them as companions to the Fibonacci sequence in his work on number theory.^[7]

Other Common Examples

One prominent companion to a Lucas sequence beyond the standard cases is the Pell-Lucas sequence, defined with parameters P = 2 and Q = -1. The first six terms, computed via the recurrence relation, are 2, 2, 6, 14, 34, 82.^[8] Another example of a companion sequence arises with P = 3 and Q = -1, yielding the sequence beginning 2, 3, 11, 36, 119, 393. This instance shares the value of Q = -1 with the companion to the Fibonacci sequence, leading to analogous structural features, though the larger P produces a shifted and accelerated growth pattern relative to Fibonacci terms. A degenerate case with repeated roots occurs when the discriminant D = P^2 - 4Q = 0, such as for P = 2 and Q = 1. In this case, the Lucas sequence terms are 0, 1, 2, 3, 4, ..., while the companion sequence terms are constantly 2: 2, 2, 2, 2, 2, 2.^[9]^[1]

Closed-Form Expressions

Distinct Roots

When the discriminant D = P^2 - 4Q > 0, the characteristic equation r^2 - P r + Q = 0 of the Lucas sequence recurrence has two distinct roots given by

\alpha = \frac{P + \sqrt{D}}{2}, \quad \beta = \frac{P - \sqrt{D}}{2}.

These roots satisfy \alpha + \beta = P and \alpha \beta = Q. For the Lucas sequence \{u_n\} with initial conditions u_0 = 0 and u_1 = 1, the closed-form expression, known as the Binet-like formula, is

u_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}.

^[1] For the companion Lucas sequence \{v_n\} with initial conditions v_0 = 2 and v_1 = P, it is

v_n = \alpha^n + \beta^n.

These formulas provide explicit ways to compute the terms without recursion when the roots are distinct real numbers. To verify the expressions satisfy the defining recurrence for n \geq 2, note that \alpha and \beta satisfy \alpha^2 = P \alpha - Q and \beta^2 = P \beta - Q. Thus, \alpha^n = P \alpha^{n-1} - Q \alpha^{n-2} and similarly for \beta. For u_n, multiplying the first by \beta^{n} and the second by \alpha^{n} and subtracting yields the form after division by \alpha - \beta. For v_n, adding the equations gives v_n = P v_{n-1} - Q v_{n-2}. The initial conditions hold: u_0 = \frac{1 - 1}{\alpha - \beta} = 0, u_1 = \frac{\alpha - \beta}{\alpha - \beta} = 1; v_0 = 1 + 1 = 2, v_1 = \alpha + \beta = P. For integer parameters P and Q, the roots \alpha and \beta are algebraic integers in the quadratic field \mathbb{Q}(\sqrt{D}). If additionally Q = \pm 1, then they are units in the ring of integers of this field (assuming D square-free).^[10]

Repeated Roots

When the discriminant D = P^2 - 4Q = 0, the characteristic equation x^2 - Px + Q = 0 has a repeated root \alpha = P/2. In this degenerate case, Q = P^2/4, and the sequences admit closed-form expressions. For the companion sequence v_n (with initial conditions v_0 = 2 and v_1 = P),

v_n = 2 \alpha^n = 2 \left( \frac{P}{2} \right)^n.

^[11] For the Lucas sequence u_n (with initial conditions u_0 = 0 and u_1 = 1),

u_n = n \alpha^{n-1} = n \left( \frac{P}{2} \right)^{n-1}.

^[11] These formulas arise as the limit of the distinct-roots expressions as \beta \to \alpha, yielding v_n = 2\alpha^n and u_n = n \alpha^{n-1} (via L'Hôpital's rule for the indeterminate form in u_n). Alternatively, they follow from the general solution to the recurrence for repeated roots, (a + b n) \alpha^n. For v_n, v_0 = a = 2 and v_1 = (2 + b) \alpha = P yield b = 0. For u_n, u_0 = a = 0 and u_1 = b \alpha = 1 yield b = 1/\alpha, so u_n = n \alpha^{n-1}. To verify for v_n, substitute into the recurrence v_n = P v_{n-1} - Q v_{n-2}:

$2 P \left( \frac{P}{2} \right)^{n-1} - \frac{P^2}{4} \cdot 2 \left( \frac{P}{2} \right)^{n-2} = \frac{2 P^n}{2^{n-1}} - \frac{P^n}{2^{n-1}} = \frac{P^n}{2^{n-1}} = 2 \left( \frac{P}{2} \right)^n.

The initial conditions hold: v_0 = 2 \cdot 1 = 2, v_1 = 2 \cdot (P/2) = P. For u_n, the general solution satisfies the recurrence by construction, and initials hold as above. For example, take P = 2 and Q = 1, so \alpha = 1 and D = 0. Then v_n = 2 \cdot 1^n = 2 for all n \geq 0, and the sequence is $2, 2, 2, 2, \dots, which satisfies v_n = 2 v_{n-1} - v_{n-2}. For u_n = n \cdot 1^{n-1} = n, the sequence is $0, 1, 2, 3, 4, \dots, which satisfies u_n = 2 u_{n-1} - u_{n-2}.^[11]

Mathematical Properties

Generating Functions

The ordinary generating function for a Lucas sequence \{V_n(P, Q)\}_{n=0}^\infty, defined by the recurrence V_n = P V_{n-1} - Q V_{n-2} for n \geq 2 with initial conditions V_0 = 2 and V_1 = P, is given by

G(x) = \sum_{n=0}^\infty V_n(P, Q) x^n = \frac{2 - P x}{1 - P x + Q x^2}.

^[12] This closed-form expression holds for arbitrary parameters P, Q \in \mathbb{C} (with appropriate convergence considerations), encompassing all cases including distinct, repeated, or complex roots of the characteristic equation t^2 - P t + Q = 0. To derive this, start with the generating function G(x) = \sum_{n=0}^\infty V_n x^n. Substituting the initial terms and the recurrence for n \geq 2 yields

G(x) = 2 + P x + \sum_{n=2}^\infty (P V_{n-1} - Q V_{n-2}) x^n.

The sums can be manipulated using shifts:

\sum_{n=2}^\infty V_{n-1} x^n = x (G(x) - 2), \quad \sum_{n=2}^\infty V_{n-2} x^n = x^2 G(x).

Thus,

G(x) = 2 + P x + P x (G(x) - 2) - Q x^2 G(x) = 2 - P x + (P x - Q x^2) G(x).

Rearranging terms gives the functional equation

G(x) (1 - P x + Q x^2) = 2 - P x,

G(x) = \frac{2 - P x}{1 - P x + Q x^2}.

^[13] This derivation relies solely on the linear recurrence and initial conditions, making it applicable regardless of the nature of the roots. When the roots \alpha and \beta of the characteristic equation are distinct (i.e., the discriminant P^2 - 4Q \neq 0), the generating function admits a partial fraction expansion. Since V_n = \alpha^n + \beta^n,

G(x) = \sum_{n=0}^\infty (\alpha^n + \beta^n) x^n = \frac{1}{1 - \alpha x} + \frac{1}{1 - \beta x} = \frac{2 - P x}{1 - P x + Q x^2},

where the equality follows from \alpha + \beta = P and \alpha \beta = Q.^[13] This form highlights the geometric series structure underlying the sequence. The radius of convergence of G(x) is \min(1/|\alpha|, 1/|\beta|), determined by the pole closest to the origin in the complex plane, which governs the asymptotic growth of V_n via \limsup_{n \to \infty} |V_n|^{1/n} = \max(|\alpha|, |\beta|).^[13]

Identities and Relations

Lucas sequences exhibit a rich collection of algebraic identities and relations that connect terms within the same sequence, relate the companion sequences U_n(P, Q) and V_n(P, Q), and link sequences defined by different parameters P and Q. A central set of identities are the addition formulas, which express V_{m+n} and U_{m+n} in terms of other terms. For the Lucas sequence V_n(P, Q), the addition formula states that

V_{m+n}(P, Q) = V_m(P, Q) V_n(P, Q) - Q^n V_{m-n}(P, Q)

for integers m \geq n \geq 0. This can be rearranged to

V_m(P, Q) V_n(P, Q) = V_{m+n}(P, Q) + Q^n V_{m-n}(P, Q).

The corresponding formula for the companion sequence is

U_{m+n}(P, Q) = U_m(P, Q) V_n(P, Q) - Q^n U_{m-n}(P, Q).

In the specific case where P = 1 and Q = -1, with U_n the Fibonacci numbers F_n and V_n the Lucas numbers L_n, the second formula specializes to d'Ocagne's identity:

F_{m+n} = F_m L_n - (-1)^n F_{m-n}.

Another key relation connects the two companion sequences through the discriminant D = P^2 - 4Q:

V_n^2(P, Q) - D U_n^2(P, Q) = 4 Q^n.

For the standard parameters P = 1, Q = -1 (where D = 5), this reduces to

L_n^2 - 5 F_n^2 = 4 (-1)^n.

Several doubling and multiple-angle identities follow directly from the addition formulas. For instance,

V_{2n}(P, Q) = V_n^2(P, Q) - 2 Q^n,

which provides a recursive way to compute even-indexed terms. A similar identity for odd indices is

V_{2n+1}(P, Q) = V_{n+1}(P, Q) V_n(P, Q) - P Q^n.

^[1] Lucas sequences with scaled parameters are related by transformation formulas derived from their closed-form expressions. Specifically, for any integer a \neq 0,

V_n(aP, a^2 Q) = a^n V_n(P, Q).

Equivalently,

V_n(P, Q) = a^n V_n\left(\frac{P}{a}, \frac{Q}{a^2}\right).

These scaling relations allow sequences with adjusted parameters to be expressed in terms of a base sequence, facilitating comparisons and computations across different parameter sets.

Divisibility Properties

Lucas sequences exhibit several notable divisibility properties, particularly concerning the relationship between terms indexed by divisors and the periodicity of the sequence modulo a fixed integer. For a Lucas sequence of the second kind V_n(P, Q), defined by the recurrence V_{n} = P V_{n-1} - Q V_{n-2} with initial conditions V_0 = 2 and V_1 = P, if m divides n and the quotient n/m is odd, then V_m divides V_n.^[14] This property, known as the entry point theorem for Lucas sequences of the second kind, holds under the assumption that the parameters P and Q are coprime integers.^[14] It contrasts with the first kind sequences U_n(P, Q), where divisibility holds without the odd quotient condition.^[14] A key concept in the divisibility structure is the rank of appearance of an integer m in a Lucas sequence, defined as the smallest positive integer k such that m divides V_k(P, Q).^[15] For prime p coprime to $2Q, this rank k divides p - (D/p), where D = P^2 - 4Q is the discriminant and (D/p) is the Legendre symbol.^[15] The rank provides insight into the first occurrence of divisibility by m, and subsequent multiples of k will also be divisible by m under the sequence's recursive properties. Lucas sequences are periodic modulo any integer m \geq 2, analogous to the Pisano period for Fibonacci numbers; the length of this period, denoted \pi(P, Q; m), is the smallest positive integer d such that V_{n+d} \equiv V_n \pmod{m} for all n \geq 0.^[16] This periodicity arises from the finite number of possible residue pairs in the recurrence modulo m. For the specific case of Lucas numbers (P=1, Q=-1), the sequence modulo m repeats with a period that shares structural similarities with the Fibonacci Pisano period, though the exact length depends on m.^[16] Specific divisibility patterns emerge for individual terms, particularly in the standard Lucas numbers L_n = V_n(1, -1). For instance, L_n is even if and only if 3 divides n, meaning every third term is divisible by 2.^[17] More generally, the greatest common divisor of two terms satisfies \gcd(L_m, L_n) = L_{\gcd(m,n)} when the 2-adic valuations of m and n are equal (i.e., the powers of 2 dividing them match); otherwise, it equals 2 if 3 divides \gcd(m,n), or 1 if not.^[18] This conditional gcd formula extends to general second-kind Lucas sequences with coprime parameters, where the result is V_d under matching 2-adic conditions, and 1 or 2 otherwise.^[18]

Connections to Diophantine Equations

Pell Equations

Lucas sequences are closely linked to the solutions of Pell equations, which are Diophantine equations of the form x^2 - d y^2 = \pm 1, where d > 0 is a square-free integer not a perfect square. For a Lucas sequence defined by integer parameters P and Q with discriminant D = P^2 - 4Q > 0, the sequences U_n(P, Q) and V_n(P, Q) (the proper Lucas sequence and its companion sequence, respectively) generate these solutions when Q = \pm 1 and D is such that d = D/4 is an integer (which occurs when P is even). In this case, the pairs (V_n/2, U_n) satisfy (V_n/2)^2 - d U_n^2 = (-Q)^n, providing all positive integer solutions to the Pell equation x^2 - d y^2 = \pm 1 for appropriate parities of n.^[19] This relation arises from the algebraic structure of real quadratic number fields \mathbb{Q}(\sqrt{d}). The roots of the characteristic equation x^2 - P x + Q = 0 are \alpha = (P + \sqrt{D})/2 and \beta = (P - \sqrt{D})/2, which serve as the fundamental unit \varepsilon = \alpha and its conjugate in the order \mathbb{Z}[\alpha] of the field, provided the norm N(\alpha) = Q = \pm 1. The Binet-like formulas express \alpha^n = (V_n + U_n \sqrt{D})/2 and \beta^n = (V_n - U_n \sqrt{D})/2, so the norm N(\alpha^n) = Q^n = (\pm 1)^n implies that \alpha^n is a unit of norm \pm 1, yielding the Pell solutions via the rational and irrational parts after scaling by 2. For instance, with P = 2 and Q = -1, D = 8, and d = 2, the equation becomes (V_n/2)^2 - 2 U_n^2 = (-1)^n, where solutions for n even solve x^2 - 2 y^2 = 1 and for n odd solve x^2 - 2 y^2 = -1.^[20]^[19] Historically, the connection between such recurrences and Pell equations traces back to the use of continued fraction expansions of \sqrt{d}, whose convergents p_k/q_k satisfy p_k^2 - d q_k^2 = (-1)^{k+1} \cdot \delta_k with bounded \delta_k, and the minimal solution corresponds to the period length of the expansion. These convergents obey linear recurrences identical in form to those of Lucas sequences, allowing the full set of solutions to be generated recursively from the fundamental solution, which aligns with powers of the unit \alpha. This approach, developed in the 18th and 19th centuries by mathematicians like Lagrange and Dirichlet, underpins the parametric representation via Lucas sequences.^[21]

Companion Pell-Lucas Equations

Companion Pell-Lucas equations are variants of the Pell equation of the form x^2 - d y^2 = \pm 4, which are solved using the Pell-Lucas sequence Q_n and the associated Pell sequence P_n for specific values of d, such as d = 2 or d = 8. These equations arise in the context of units in quadratic orders and provide infinite families of solutions through the recurrence relations of the sequences. The Pell-Lucas numbers are defined by the recurrence Q_n = 2 Q_{n-1} + Q_{n-2} with initial conditions Q_0 = 2, Q_1 = 2, while the Pell numbers satisfy P_n = 2 P_{n-1} + P_{n-2} with P_0 = 0, P_1 = 1. A fundamental identity linking these sequences is

\left( \frac{Q_n}{2} \right)^2 - 2 P_n^2 = (-1)^n,

which solves the equation x^2 - 2 y^2 = \pm 1 with x = Q_n/2 and y = P_n (noting that Q_n is always even), where the sign is negative for odd n and positive for even n. Scaling this identity by 4 yields

Q_n^2 - 8 P_n^2 = 4 (-1)^n,

providing solutions to x^2 - 8 y^2 = \pm 4 with x = Q_n and y = P_n. For even n = 2k, this corresponds to the positive case x^2 - 8 y^2 = 4, reflecting units of norm 1 in the order \mathbb{Z}[\sqrt{2}] of the quadratic field \mathbb{Q}(\sqrt{2}), where the Pell-Lucas numbers generate the rational parts of powers of the fundamental unit $1 + \sqrt{2}. Similarly, for odd n, the negative case arises from units of norm -1. These forms are essential for studying associate units and have applications in number theory, such as determining fundamental solutions in related Diophantine problems. In the broader context of Lucas sequences, the Pell-Lucas case exemplifies how the V_n terms (here Q_n) directly contribute to solving these companion equations without relying on additional companion sequences beyond the paired U_n (here P_n). For instance, the solutions to x^2 - 2 y^2 = -1 are given by x = Q_{2k-1}/2, y = P_{2k-1} for positive integers k, generating infinite solutions like (1, 1), (7, 5), (41, 29). This contrasts with the standard Pell equation x^2 - 2 y^2 = 1, whose solutions involve even indices, highlighting the companion role of the Pell-Lucas sequence in addressing the negative norm case. Further variants, such as those derived from polygonal numbers in the Pell sequence, lead to more complex equations like $2x^2 = y^2 (3y - 1)^2 \pm 2, whose complete integer solutions are finite and can be verified using properties of the Pell-Lucas numbers.^[22]

Specific Named Sequences

Lucas Numbers

The Lucas numbers form a specific instance of the Lucas sequence with parameters P = 1 and Q = -1, defined by the initial values L_0 = 2, L_1 = 1, and the recurrence relation L_n = L_{n-1} + L_{n-2} for n \geq 2. This yields the sequence 2, 1, 3, 4, 7, 11, 18, 29, 47, ... . They are intimately related to the Fibonacci sequence \{F_n\}, where F_0 = 0, F_1 = 1, and F_n = F_{n-1} + F_{n-2} for n \geq 2, via the identity L_n = F_{n-1} + F_{n+1} for n \geq 1.^[4]^[23] The closed-form expression for the Lucas numbers, analogous to Binet's formula for the Fibonacci numbers, is given by

L_n = \phi^n + \psi^n,

where \phi = \frac{1 + \sqrt{5}}{2} is the golden ratio and \psi = \frac{1 - \sqrt{5}}{2} is its conjugate. This formula arises from solving the characteristic equation of the recurrence and holds for all integers n \geq 0.^[4] A distinctive parity property of the Lucas numbers is that L_n is even if and only if n is a multiple of 3; otherwise, L_n is odd. For example, L_3 = 4 (even), L_6 = 18 (even), while L_1 = 1, L_2 = 3, L_4 = 7, and L_5 = 11 are all odd. Additionally, the sum of the first n Lucas numbers starting from L_1 is \sum_{k=1}^n L_k = L_{n+2} - 3. This can be verified by induction: it holds for n=1 since L_3 - 3 = 4 - 3 = 1 = L_1, and assuming it for n-1, the sum to n is (L_{n+1} - 3) + L_n = L_{n+2} - 3.^[6]^[23] Lucas numbers that are prime, known as Lucas primes, include small examples such as L_4 = 7, L_5 = 11, L_7 = 29, L_{11} = 199, and L_{13} = 521. These primes play a role in number-theoretic studies, including primality testing inspired by Édouard Lucas's original work on the sequence. As of 2025, the largest known probable Lucas prime is L_{1051849}, a number with 219,824 decimal digits, discovered through computational searches for large terms in the sequence.^[24] The Pell-Lucas numbers Q_n form a specific instance of the Lucas sequence V_n(P, Q) with parameters P = 2 and Q = -1.^[8] They satisfy the recurrence relation Q_n = 2 Q_{n-1} + Q_{n-2} for n \geq 2, with initial conditions Q_0 = 2 and Q_1 = 2, generating the sequence 2, 2, 6, 14, 34, 82, 198, ....^[8] These numbers are closely related to the Pell numbers P_n, which are the companion Lucas sequence U_n(2, -1) starting with P_0 = 0, P_1 = 1, via the identity Q_n = P_{n-1} + P_{n+1}.^[8] Key properties of the Pell-Lucas numbers include their Binet formula Q_n = (1 + \sqrt{2})^n + (1 - \sqrt{2})^n, which highlights their growth rate asymptotically approaching (1 + \sqrt{2})^n for large n.^[8] All terms are even integers, and they satisfy the Diophantine identity Q_n^2 - 8 P_n^2 = 4 (-1)^n, linking them directly to solutions of the Pell equation x^2 - 2 y^2 = \pm 4.^[8] Additional relations include Q_n^2 = 4 (2 P_n^2 + (-1)^n) and Q_{2n} = Q_n^2 - 2 (-1)^n.^[8] Other notable sequences in this family include the Jacobsthal numbers, defined as the Lucas sequence U_n(1, -2), with terms 0, 1, 1, 3, 5, 11, 21, ... following the recurrence J_n = J_{n-1} + 2 J_{n-2} and initial conditions J_0 = 0, J_1 = 1.^[25] The companion Jacobsthal-Lucas sequence V_n(1, -2) starts 2, 1, 5, 7, 17, 31, ... and shares similar properties, used in combinatorial contexts.^[26] Lehmer sequences are a broader class generalizing Lucas sequences by replacing the parameter P with \sqrt{R} for some integer R, often studied for their primitive prime divisors in number theory. In modern applications, Pell-Lucas numbers have been employed in coding theory through matrix-based encoding and decoding methods, leveraging their recurrence for constructing cyclic codes with desirable properties like minimum distance. Similarly, Jacobsthal and Jacobsthal-Lucas sequences support coding schemes via their matrix representations.^[27] These sequences are implemented in computational tools such as SageMath, which provides classes for binary recurrence sequences including general Lucas sequences for numerical exploration and verification.^[28]

Applications

Number Theory and Algebra

Lucas sequences play a significant role in primality testing within number theory, particularly through the Lucas-Lehmer test for verifying the primality of Mersenne numbers of the form M_p = 2^p - 1, where p is prime. The test defines a sequence s_0 = 4, s_i = s_{i-1}^2 - 2 \pmod{M_p} for i \geq 1, and declares M_p prime if s_{p-2} \equiv 0 \pmod{M_p}. This sequence corresponds to terms of the Lucas sequence V_n(4, 1) evaluated at powers of 2, leveraging the algebraic structure of the recurrence to detect factors efficiently in the ring \mathbb{Z}[\sqrt{3}] or related extensions.^[29] The test's deterministic nature and subexponential time complexity make it indispensable for discovering large Mersenne primes, as implemented in projects like GIMPS.^[29] In analytic number theory, Lucas sequences provide tools for establishing quadratic reciprocity and addressing related problems, such as those involving class numbers of quadratic fields. Specifically, for Lucas sequences \{y_n\} defined by y_0 = 0, y_1 = 1, y_{n+1} = A y_n + B y_{n-1}, generating functions relate the terms to the Legendre symbol (\cdot / q) via formal power series identities in \mathbb{Q}[], yielding proofs of quadratic reciprocity from integrality conditions.^[30] Congruences like L_{k p} \equiv \left( \frac{p}{5} \right) L_k \pmod{p} for odd primes p and the standard Lucas sequence L_n link sequence values to quadratic characters, analogous to the Legendre symbol, facilitating computations of splitting behaviors in quadratic extensions and contributions to class number formulas through Dirichlet L-functions.^[31] These properties extend to higher reciprocity laws via generalized Lucas sequences, aiding in the determination of ideal class groups.^[30] Algebraically, Lucas sequences represent units in real quadratic fields \mathbb{Q}(\sqrt{d}) for square-free d > 0. The companion sequence V_n(P, Q) satisfies V_n(P, Q) = \alpha^n + \beta^n, where \alpha, \beta = \frac{P \pm \sqrt{P^2 - 4Q}}{2} are roots of the characteristic equation x^2 - P x + Q = 0. In \mathbb{Q}(\sqrt{d}), if \varepsilon is the fundamental unit, the sequence \{\varepsilon^n + \overline{\varepsilon}^n\}_{n \geq 0} forms a Lucas sequence with P = \varepsilon + \overline{\varepsilon}, Q = -\varepsilon \overline{\varepsilon} = \pm 1, capturing the unit group structure.^[32] The Galois group \mathrm{Gal}(\mathbb{Q}(\sqrt{d})/\mathbb{Q}) acts by conjugation, swapping \alpha and \beta, which preserves the integer-valued sequence and underscores its role in algebraic number theory, such as studying regulator ideals and unit norms.^[32]

Combinatorics and Graph Theory

Lucas sequences appear prominently in enumerative combinatorics through their role in counting tilings and lattice paths. The Lucas numbers, a specific instance of Lucas sequences with parameters P=1 and Q=-1, enumerate the number of ways to tile a circular n-board using monominoes (squares) and dominoes, where the circular arrangement accounts for rotational symmetry in the placements. This interpretation extends to phased tilings of linear boards, where the phase of the final tile (distinguishing between domino and square endings) leads to recurrences matching the Lucas sequence definition L_n = L_{n-1} + L_{n-2} with initial conditions L_0 = 2, L_1 = 1. For generalized Lucas sequences \{U_n(P, Q)\}, similar tiling models with weighted monominoes (weight P) and dominoes (weight -Q) yield combinatorial proofs of identities, such as those relating Fibonacci and Lucas terms.^[33] In lattice path enumerations, Lucas analogues of binomial coefficients, known as Lucasnomials \dbinom{n}{k}_{\{s,t\}}, count weighted paths from (k, 0) to (0, n) within a staircase Young diagram \delta_n. These paths consist of north and west steps, grouped into blocks (e.g., NI for north immediately after west, NL otherwise), with weights derived from the sequence parameters s and t, where the total weight sums to the Lucasnomial. This model provides a natural bijection for proving log-concavity and other properties of Lucas sequences, extending classical binomial interpretations to more general recurrences. For instance, Catalan numbers as specializations (s=3, t=-1) count Dyck-like paths in \delta_{2n}, weighted by factorials of Lucas terms.^[34] In graph theory, Lucas sequences count structural elements such as spanning trees in specific graph families. The number of spanning trees in a labeled wheel graph W_n on n+1 vertices (a cycle with an additional hub vertex connected to all cycle vertices) is given by L_{2n-2}, where L_m is the m-th Lucas number. This result arises from recursive decompositions of the wheel into paths and cycles, leveraging the transfer matrix method or inclusion-exclusion over compositions of n. Similarly, for fan graphs (a hub connected to a path of n vertices), related counts involve Fibonacci numbers, but generalizations to labeled variants incorporate Lucas terms through even-indexed evaluations. These enumerations highlight the sequences' utility in recursive graph counting.^[35] Lucas sequences also encode independence polynomials in cycle and path graphs. The number of independent sets in an n-vertex cycle graph C_n is precisely L_n, reflecting the closed-loop constraint that aligns with the Lucas recurrence. This extends to generalized graphs like chainsaw graphs C(n, a, b), where i(C(n, a, b)), the number of independent sets, equals the n-th term of the Lucas sequence of the second kind V_n(a, -b), defined by V_n = P V_{n-1} - Q V_{n-2}. For path variants (broken chainsaws), the count follows the first-kind sequence U_{n+2}(a, -b). These interpretations provide graph-theoretic proofs for properties of Dickson polynomials, which are closely related to Lucas sequences.^[36] Recent combinatorial applications include graph coloring enumerations. In generalized circular chord graphs C_n^{(3)} (n-cycles augmented with chords at distance 3), the chromatic polynomial evaluated at 3 colors for odd n incorporates the Lucas number L_n directly: P(C_n^{(3)}, 3) = L_n + 2 \cos(2\pi n / 3) + 2 s_n + 2, where s_n satisfies a cubic recurrence. This structure arises from transfer matrix analysis of coloring constraints around the cycle, with asymptotic growth dominated by \phi^n (golden ratio), underscoring Lucas sequences' role in polynomial recurrences for graph invariants. Generating functions for such counts often reference Lucas terms briefly to capture partition-like color distributions, though explicit distinct-parts partitions remain less directly tied.^[37]

References

[1]
Lucas Sequence -- from Wolfram MathWorld
The sequences are called Lucas sequences, where the definition is usually extended to include U_(-1)=(a^(-1)-b^(-1))/(ab)=(-1)/(ab)=-1/Q.
[2]
[PDF] Introduction to Lucas Sequences
Dec 14, 2017 · Lucas sequences play important roles in number theory and combinatorics. In this talk we introduce various properties of Lucas sequences and ...
[3]
Lucas Number -- from Wolfram MathWorld
The Lucas numbers are the sequence of integers {L_n}_(n=1)^infty defined by the linear recurrence equation L_n=L_(n-1)+L_(n-2) with L_1=1 and L_2=3.
[4]
[PDF] Fibonacci and Lucas Sequences
The Lucas sequence is defined by L0 = 2, L1 = 1, and Ln+2 = Ln+1 + Ln, for n ≥ 0. So they satisfy the same recurrence relation with different initial values.
[5]
A000032 - OEIS
### Summary of Relations Between Lucas and Fibonacci Numbers
[6]
Édouard Lucas (1842 - 1891) - Biography - MacTutor
Lucas is best known for his results in number theory: in particular he studied the Fibonacci sequence and the associated Lucas sequence is named after him.
[7]
Pell-Lucas Number -- from Wolfram MathWorld
The Pell-Lucas numbers are the V_n s in the Lucas sequence with P=2 and Q=-1, and correspond to the Pell-Lucas polynomial Q_n(1).
[8]
[PDF] The Terms in Lucas Sequences Divisible by Their Indices
Then the well-known Lucas sequence of the first kind (or generalised Fibonacci sequence) ... P = 3,Q = 2, where un = 2n − 1, vn = 2n + 1. Here S = {1} as ∆ = 1, ...<|control11|><|separator|>
[9]
https://cs.uwaterloo.ca/journals/JIS/VOL13/Smyth/smyth2.pdf
[10]
[PDF] Identities and Generating Functions of Products of Generalized ...
Jun 5, 2024 · We use the relation between generalized Fibonacci and Lucas numbers. We obtain the generating function for generalized Lucas numbers. QL(x) ...
[11]
[PDF] generatingfunctionology - Penn Math
May 21, 1992 · This book is about generating functions and some of their uses in discrete mathematics. The subject is so vast that I have not attempted to give ...
[12]
[PDF] Lucas sequences and divisibility sequences. Peter Bala, May 2016
if n divides m and m/n is odd then L(n) divides L(m). We shall refer to sequences having this property as odd divisibility sequences. Somewhat surprisingly ...Missing: L_m L_n
[13]
[PDF] Congruences Involving Sums of Ratios of Lucas Sequences
Aug 12, 2014 · The assertions about the ranks of appearance in the examples were checked using the computer algebra system magma. Lucas sequences are well- ...
[14]
[PDF] Blocks within the period of Lucas sequence - Eiris
For any modulo m, it is easy to observe that the sequence {Ln} is always periodic and it repeats from starting values 0 and. 1. By kL = kL(m), we mean the ...
[15]
[PDF] common factors in series of consecutive terms of associated lucas ...
Observe that the recurrence relation (2.1) gives us that every third Lucas number is even, hence by 3 | t0+84, Lt0+84 is even and cannot be coprime to all the ...
[16]
[PDF] THE G.C.D. IN LUCAS SEQUENCES AND LEHMER NUMBER ...
It is interesting that the values of all three of these gcd's can be rather easily found, for all pairs of positive integers m and n, by the application of an ...Missing: terms | Show results with:terms
[17]
[PDF] representation of solutions of pell equations using lucas sequences
Representation of solutions of Pell equations using Lucas sequences. 77. Before giving the proof we mention that the purpose of the hypothesis 3B+5 ≤. 2A is ...
[18]
None
### Summary: Generalization of Fibonacci and Lucas Sequences to Quadratic Fields
[19]
[PDF] Solving Diophantine equations via Lucas-Lehmer theory
Continued fractions play a vital role in the solutions of Pell's equations x2 − Dy2 = ±1. Moreover, the theory of E. Lucas and D.H. Lehmer together.
[20]
[PDF] PENTAGONAL NUMBERS IN THE PELL SEQUENCE AND ...
V. Siva Rama Prasad & B. Srinivasa Rao. "Pentagonal Numbers in the Associated Pell. Sequence and Diophantine Equations x2(3x-l)2 = ...
[21]
The Lucas Numbers - Dr Ron Knott
Lucas numbers, named after Edouard Lucas, are 2, 1, 3, 4, 7, 11, 18, ... and follow the rule L_n = L_n-1 + L_n-2, starting with 2 and 1.A number trick based on Phi... · What's the secret? · An even more complicated...Missing: initial conditions
[22]
Lucas Prime -- from Wolfram MathWorld
The first few prime Lucas numbers L_n are 2, 3, 7, 11, 29, 47, 199, 521, 2207, 3571, ... (OEIS A005479), corresponding to indices n=0, 2, 4, 5, 7, 8, 11, ...
[23]
Jacobsthal Number -- from Wolfram MathWorld
The Jacobsthal numbers are the numbers obtained by the U_ns in the Lucas sequence with P=1 and Q=-2, corresponding to a=2 and b=-1.
[24]
Jacobsthal and Jacobsthal-Lucas Numbers - Tutorials Point
Sep 28, 2023 · Jacobsthal Numbers Lucas sequence 𝑈𝑛(𝑃,𝑄) where P = 1 and Q = -2 are called Jacobsthal numbers. The recurrence relation for Jacobsthal ...
[25]
Lehmer sequence - Wikipedia
... Lehmer sequence is divided by √R compared to the corresponding Lucas sequence. That is, when R = P2 the Lehmer and Lucas sequences are related as: P U 2 n ...
[26]
Applications of Jacobsthal and Jacobsthal-Lucas numbers in coding ...
In this article, we have developed a new method for coding\decoding the Jacobsthal and Jacobsthal-Lucas sequences via matrix representations.
[27]
Binary Recurrence Sequences - Combinatorics
This function works for degenerate sequences as well. Sage. sage: S ... Lucas sequence sage: S.pthpowers(3,10**10) # long time (3 seconds) ...
[28]
[PDF] THE LUCAS–LEHMER TEST 1. Introduction If 2n
Introduction. If 2n − 1 is prime then n is prime, since n = ab =⇒ 2n − 1 = (2a)b − 1 = (2a − 1)(2a(b-1) + 2a(b-2) + ··· + 2a + 1).
[29]
[PDF] QUADRATIC RECIPROCITY VIA LUCAS SEQUENCES Paul ...
Lucas sequences, defined by a recurrence, are used to prove quadratic reciprocity via formal power series and integrality relations.
[30]
[PDF] On Fibonacci and Lucas sequences modulo a prime and primality ...
) denotes the Legendre symbol. The equivalent result for the Lucas numbers is also derived as part of the same theorem. Results of similar flavor were ...
[31]
The sequences of Fibonacci and Lucas for each real quadratic fields ...
Apr 30, 2019 · We construct the sequences of Fibonacci and Lucas at any quadratic field \mathbb{Q}(\sqrt{d}\ ) with d>0 square free.Missing: roots | Show results with:roots
[32]
[PDF] PHASED TILINGS AND GENERALIZED FIBONACCI IDENTITIES ...
Two important special cases are the classical Fibonacci sequence Fn. (FQ = 0 and FX = T) and the Lucas sequence Ln (LQ = 2 and Lx = 1). These sequences satisfy ...
[33]
[PDF] Combinatorial interpretations of Lucas analogues of binomial ... - arXiv
Sep 24, 2018 · The purpose of this paper is to give a new, even more natural model for these Lucasnomials using lattice paths which can be used to prove ...
[34]
[PDF] SPANNING TREES AND FIBONACCI AND LUCAS NUMBERS
For n > 2 the number of spanning trees of a labelled wheel on n + 1 points is L. 2n - 2, and the number of span- ning trees of a labelled fan on n + 1 points ...Missing: sequences | Show results with:sequences
[35]
[PDF] a graph-theoretic encoding of lucas sequences
Aug 21, 2015 · We then use this class of graphs to provide new combinatorial interpretations of the terms of Dickson polynomials of the first and second kind.
[36]
https://www.fq.math.ca/Papers1/53-3/AlexHeard01232015.pdf