Lucas number
The Lucas numbers form an integer sequence named after the French mathematician Édouard Lucas (1842–1891), defined by the linear recurrence relation L_n = L_{n-1} + L_{n-2} for n \geq 2, with initial conditions L_0 = 2 and L_1 = 1.[1][2] The first few terms are 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, and so on.[3] This sequence serves as the companion to the Fibonacci numbers, which follow the same recurrence but start with F_0 = 0 and F_1 = 1, and the two sequences are intimately related through identities such as L_n = F_{n-1} + F_{n+1} for n \geq 1.[4] Like the Fibonacci sequence, Lucas numbers possess a closed-form expression via Binet's formula: L_n = \phi^n + (1 - \phi)^n, where \phi = \frac{1 + \sqrt{5}}{2} is the golden ratio (approximately 1.618).[5] This formula yields exact integers despite involving irrational numbers, highlighting their deep connection to the golden ratio.[4] Lucas introduced the sequence in his studies of recursive number patterns during the 1870s and 1880s, building on earlier work with Fibonacci-like series to explore properties in number theory.[6] His investigations, detailed in publications like Théorie des nombres (published posthumously in 1891), emphasized their role alongside Fibonacci numbers in generating functions, divisibility, and modular arithmetic.[7] Notable properties include the fact that every Lucas number is the sum of the two nearest Fibonacci numbers straddling it, and they exhibit similar growth rates to the Fibonacci numbers, with L_n \approx \phi^n for large n.[5] In applications, Lucas numbers appear in primality testing, such as the Lucas-Lehmer test for Mersenne primes, where sequences based on them help verify the primality of numbers of the form $2^p - 1.[1] They also feature in combinatorial problems, matrix representations of recurrences, and extensions to generalized Lucas sequences with parameters P and Q, which unify various linear recurrences in algebra and geometry.[8] These sequences continue to be studied for their periodic behavior modulo primes and connections to elliptic curves, underscoring their enduring significance in pure and applied mathematics.Definition and History
Definition
The Lucas numbers form an integer sequence \{L_n\}_{n=0}^\infty defined by the recurrence relation L_n = L_{n-1} + L_{n-2} \quad \text{for } n \geq 2, with initial conditions L_0 = 2 and L_1 = 1.[3][9] The first few terms of the sequence are L_0 = 2, L_1 = 1, L_2 = 3, L_3 = 4, L_4 = 7, L_5 = 11, L_6 = 18, L_7 = 29, L_8 = 47, and so on (OEIS A000032).[10] The Lucas numbers constitute a particular instance of the more general Lucas sequences V_n(P, Q), obtained by setting the parameters P = 1 and Q = -1.[11] Like the Fibonacci numbers, the Lucas numbers obey the same linear recurrence but differ in their starting values.[3]History
The Lucas numbers are named after the French mathematician François Édouard Anatole Lucas (1842–1891), who first systematically studied the sequence in the 1870s as part of his investigations into integer sequences related to the Fibonacci numbers and applications in number theory.[12][13] Lucas's work on these sequences emerged during his broader research on primality testing, including methods for verifying Mersenne primes, which connect to the study of perfect numbers through the even perfect number theorem. In 1878, he published his seminal paper "Théorie des fonctions numériques simplement périodiques" in the American Journal of Mathematics, where he formalized the general class of Lucas sequences, including the specific case now known as the Lucas numbers, and introduced criteria for primality using these sequences—later refined into the Lucas-Lehmer test.[12][14] Following Lucas's death in 1891, the sequence gained wider recognition in the 20th century through recreational mathematics literature, which explored its properties alongside Fibonacci numbers in puzzles and patterns. The sequence was formally cataloged in the On-Line Encyclopedia of Integer Sequences (OEIS) upon its founding in 1964 by Neil Sloane, marking its integration into modern computational and combinatorial studies.[15][16]Mathematical Foundations
Closed-Form Expression
The closed-form expression for the Lucas number L_n is given by Binet's formula: 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.[9][17] This formula arises from solving the linear recurrence relation L_n = L_{n-1} + L_{n-2} for n \geq 2, with initial conditions L_0 = 2 and L_1 = 1. The characteristic equation is r^2 - r - 1 = 0, which has roots \phi and \psi. The general solution is thus L_n = A \phi^n + B \psi^n. Applying the initial conditions yields A + B = 2 and A \phi + B \psi = 1. Since \phi + \psi = 1 and \phi \psi = -1, solving the system gives A = 1 and B = 1.[17] The expression \phi^n + \psi^n evaluates to an integer for all nonnegative integers n, despite \phi and \psi being irrational algebraic conjugates in the quadratic field \mathbb{Q}(\sqrt{5}). This integer nature follows from the fact that the powers of these conjugates, when summed, lie in the rational subfield \mathbb{Q}, and the sequence satisfies the integer-coefficient recurrence with integer initial values.[9][17] An equivalent form is L_n = \phi^n + (-\phi)^{-n}, which highlights that L_n is the exact value obtained without approximation. For n \geq 2, L_n is also the nearest integer to \phi^n, since |\psi^n| < 0.5. The Lucas numbers grow exponentially as L_n \sim \phi^n for large n, reflecting the dominant role of the golden ratio in the formula.[9][17]Relation to Fibonacci Numbers
The Lucas numbers and Fibonacci numbers are intimately connected through their shared linear recurrence relation. Both sequences satisfy the recurrence X_n = X_{n-1} + X_{n-2} for n \geq 2, with the Fibonacci sequence defined by initial conditions F_0 = 0, F_1 = 1, and the Lucas sequence by L_0 = 2, L_1 = 1.[18] This common recurrence implies that they share the same characteristic equation x^2 - x - 1 = 0, with roots \phi = \frac{1 + \sqrt{5}}{2} (the golden ratio) and \hat{\phi} = \frac{1 - \sqrt{5}}{2}.[18] A direct explicit relation expresses each Lucas number as the sum of two Fibonacci numbers: L_n = F_{n-1} + F_{n+1} for n \geq 1.[18] This formula highlights how Lucas numbers emerge from adjacent Fibonacci terms shifted by one index, illustrating a simple additive pattern between the sequences. For example, L_4 = F_3 + F_5 = 2 + 5 = 7. Visually, this relation manifests in patterns where Lucas numbers approximate sums of every other Fibonacci number in certain geometric arrangements, such as tiled rectangles or spiral approximations, though the sequences interleave distinctly due to differing initial values.[18] The connection extends to matrix representations, where both sequences arise from powers of the companion matrix Q = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}. Specifically, Q^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} for n \geq 1, and the trace of this matrix equals L_n = F_{n+1} + F_{n-1}, unifying the sequences through linear algebra.[19] Cassini-like identities further link the sequences. The standard Cassini identity for Fibonacci numbers states F_{n+1} F_{n-1} - F_n^2 = (-1)^n.[19] A related identity combining both is L_n^2 - 5 F_n^2 = 4 (-1)^n, which extends the Cassini form by incorporating the discriminant of the characteristic equation and reveals the interplay between the sequences' growth rates.[18]Sequence Extensions
Negative Indices
The Lucas sequence, defined by the recurrence L_n = L_{n-1} + L_{n-2} for n \geq 2 with initial conditions L_0 = 2 and L_1 = 1, can be extended to negative indices by solving the recurrence relation in the reverse direction. Starting from these initial values, L_{-1} is found by rearranging the equation for n=1: L_1 = L_0 + L_{-1}, so $1 = 2 + L_{-1} yields L_{-1} = -1. Similarly, L_{-2} follows from n=0: L_0 = L_{-1} + L_{-2}, so $2 = -1 + L_{-2} gives L_{-2} = 3. Continuing, L_{-3} = L_{-1} - L_{-2} = -1 - 3 = -4, and L_{-4} = L_{-2} - L_{-3} = 3 - (-4) = 7.[20][21] This backward extension preserves the same linear recurrence for all integers n, resulting in the reflection formula L_{-n} = (-1)^n L_n for positive integers n > 0. This relation holds because the characteristic equation of the recurrence remains unchanged, and induction confirms it aligns with the computed values: for n=1, L_{-1} = (-1)^1 \cdot 1 = -1; for n=2, L_{-2} = (-1)^2 \cdot 3 = 3; for n=3, L_{-3} = (-1)^3 \cdot 4 = -4. The formula can be derived by assuming the recurrence applies bidirectionally and verifying via the generating function or matrix representation of the sequence.[20][21] The closed-form Binet expression for Lucas numbers, L_n = \phi^n + \hat{\phi}^n where \phi = \frac{1 + \sqrt{5}}{2} and \hat{\phi} = \frac{1 - \sqrt{5}}{2}, extends naturally to negative indices, but direct substitution confirms L_{-n} = \phi^{-n} + \hat{\phi}^{-n} = (-1)^n L_n due to the properties \hat{\phi} = -1/\phi and \phi \hat{\phi} = -1. This verification ensures the formula's consistency across all integers without altering the integer-valued nature of the sequence.[22][20] Regarding parity, the signs for negative indices alternate based on whether the absolute value of the index is even or odd: values at even negative indices (like L_{-2} = 3, L_{-4} = 7) are positive, while those at odd negative indices (like L_{-1} = -1, L_{-3} = -4) are negative, mirroring the positive sequence but with the sign flip encoded in (-1)^n. This pattern emerges directly from the reflection formula and the recurrence's linear structure.[21][20]Lucas Polynomials
The Lucas polynomials L_n(x) form a sequence of polynomials generalizing the Lucas numbers, defined by the recurrence relation L_n(x) = x L_{n-1}(x) + L_{n-2}(x) for n \geq 2, with initial conditions L_0(x) = 2 and L_1(x) = x. These polynomials are monic of degree n for n \geq 1, and they satisfy the same linear recurrence structure as the Lucas sequence but with coefficients depending on x.[23] When evaluated at x = 1, the Lucas polynomials recover the standard Lucas numbers: L_n(1) = L_n, where L_n denotes the n-th Lucas number. For example, L_2(x) = x^2 + 2, \quad L_3(x) = x^3 + 3x, and higher-degree terms follow the pattern of expanding through the recurrence.[23] The ordinary generating function for the Lucas polynomials is \sum_{n=0}^{\infty} L_n(x) t^n = \frac{2 - x t}{1 - x t - t^2}. This closed form arises from solving the recurrence and incorporating the initial conditions. The Lucas polynomials L_n(x) are of degree n and possess roots that lie on the imaginary axis, specifically at $2i \sin(k\pi/n) for k = 1, \dots, n-1.[23] These roots are connected to the Chebyshev polynomials of the first kind via the relation L_n(x) = 2 i^n T_n\left( -i x / 2 \right), where T_n is the n-th Chebyshev polynomial, highlighting their trigonometric structure.[24]Identities and Properties
Fundamental Identities
The fundamental identities of Lucas numbers provide algebraic relations that connect terms within the sequence and link them to Fibonacci numbers. These identities are essential for deriving higher-level properties and have been established through methods such as mathematical induction and Binet's closed-form expression.[25] One key addition formula expresses L_{m+n} in terms of Lucas and Fibonacci numbers: L_{m+n} = L_{m+1} F_n + L_m F_{n-1} This symmetric form holds for positive integers m and n, and can be verified by direct computation for small values or proved using Binet's formulas for both sequences, where the powers of the golden ratio \phi = (1 + \sqrt{5})/2 and its conjugate align to yield the relation. An equivalent expression is L_{m+n} = \frac{1}{2} (L_m L_n + 5 F_m F_n), which rearranges to highlight the product of Lucas terms adjusted by Fibonacci contributions.[25][26] The multiplication formula relates the product of two Lucas numbers to others in the sequence: L_m L_n = L_{m+n} + (-1)^n L_{m-n} This identity assumes m \geq n > 0 and follows from the addition formula combined with the known relation L_k^2 - 5 F_k^2 = 4 (-1)^k; a proof by induction on n confirms it, with the base case n=1 reducing to L_m L_1 = L_{m+1} + (-1)^1 L_{m-1}, which aligns with the recurrence.[26] D'Ocagne's identity mixes Lucas and Fibonacci terms to yield another Fibonacci expression: F_m L_n = F_{m+n} + (-1)^n F_{m-n} For m \geq n \geq 0, this can be rearranged as L_m F_n - F_m L_n = (-1)^{n+1} (F_{m-n} L_n - F_n L_{m-n}), but the primary form is derived using Binet's formula, where the difference of powers simplifies due to the orthogonal properties of \phi and its conjugate. The symmetric version F_n L_m = F_{m+n} + (-1)^m F_{n-m} holds similarly.[9] An adaptation of Catalan's identity for Lucas numbers generalizes the Cassini-like relation: L_{n+r} L_{n-r} - L_n^2 = (-1)^{n-r} 5 F_r^2 This holds for integers n > r \geq 1, with the special case r=1 giving L_{n+1} L_{n-1} - L_n^2 = 5 (-1)^{n-1}. Proofs proceed by induction on r, leveraging the recurrence and the fundamental relation L_n^2 - 5 F_n^2 = 4 (-1)^n, or directly via Binet's formula, where the cross terms cancel to produce the Fibonacci square factor scaled by 5.[26]Generating Function
The ordinary generating function for the Lucas sequence \{L_n\}_{n=0}^\infty, defined by L_0 = 2, L_1 = 1, and L_n = L_{n-1} + L_{n-2} for n \geq 2, is given by G(x) = \sum_{n=0}^\infty L_n x^n = \frac{2 - x}{1 - x - x^2}, for |x| < 1/\phi \approx 0.618, where \phi = (1 + \sqrt{5})/2 is the golden ratio.[27] To derive this, start with the recurrence relation and initial conditions. Multiply the recurrence by x^n and sum over n \geq 2: \sum_{n=2}^\infty L_n x^n = \sum_{n=2}^\infty L_{n-1} x^n + \sum_{n=2}^\infty L_{n-2} x^n. The left side is G(x) - L_0 - L_1 x. The first sum on the right is x (G(x) - L_0), and the second is x^2 G(x). Substituting the initial values yields G(x) - 2 - x = x(G(x) - 2) + x^2 G(x), which simplifies to G(x) (1 - x - x^2) = 2 - x, solving for the stated formula.[28] This generating function relates closely to that of the Fibonacci sequence \{F_n\}_{n=0}^\infty, where F_0 = 0, F_1 = 1, and the same recurrence holds, with \sum_{n=0}^\infty F_n x^n = \frac{x}{1 - x - x^2}. The numerators differ due to the initial conditions: the Lucas numerator $2 - x reflects L_0 + (L_1 - L_0) x = 2 - x, while the Fibonacci is simply x.[27] The generating function connects to the closed-form Binet expression L_n = \phi^n + \psi^n, where \psi = (1 - \sqrt{5})/2 = 1 - \phi. Summing the geometric series gives G(x) = \sum_{n=0}^\infty (\phi^n + \psi^n) x^n = \frac{1}{1 - \phi x} + \frac{1}{1 - \psi x}. Partial fraction decomposition confirms this equals (2 - x)/(1 - x - x^2), as the roots of the denominator are \phi and \psi.[27] Applications include extracting coefficients L_n using the partial fractions above or via contour integrals around the poles at x = 1/\phi and x = 1/\psi, though the Binet form is more direct for computation. Generating functions also facilitate proofs of identities by series manipulation, such as multiplying G(x) by (1 - x - x^2) to recover the recurrence or deriving summation formulas through differentiation and integration.[28]Congruence Relations
The Lucas sequence is periodic modulo any positive integer m, with the length of the minimal period denoted \pi_L(m), analogous to the Pisano period for the Fibonacci sequence. This period satisfies \pi_L(m) = \pi(m) whenever \gcd(m, 5) = 1, but may differ otherwise; for example, \pi_L(5^n) = 4 \cdot 5^{n-1} for n \geq 1.[29] Representative examples illustrate this periodicity. Modulo 2, the sequence begins 1, 1, 0 and repeats every 3 terms: L_n \equiv 0 \pmod{2} if n \equiv 0 \pmod{3}, and L_n \equiv 1 \pmod{2} otherwise.[30] Modulo 3, the sequence is 1, 0, 1, 1, 2, 0, 2, 2 and repeats every 8 terms.[31] For a prime p, the rank of apparition \rho_L(p) (also called the entry point) is the smallest positive integer k such that L_k \equiv 0 \pmod{p}, provided such a k exists. This is the law of appearance for Lucas numbers. For p = 2, \rho_L(2) = 3. The prime 5 divides no Lucas number, so \rho_L(5) is undefined. For odd primes p \neq 5, \rho_L(p) always exists, divides p - \left( \frac{5}{p} \right) (where \left( \frac{5}{p} \right) is the Legendre symbol), and the period satisfies \pi_L(p) \in \{\rho_L(p), 2\rho_L(p), 4\rho_L(p)\}.[29] The primes p for which \rho_L(p) exists (i.e., those dividing some L_n) form a set of asymptotic density $2/3.[32] Basic modular properties of Lucas numbers relate to quadratic residues. Specifically, L_n \equiv 0 \pmod{p} if and only if \rho_L(p) divides n. For example, if 5 is a quadratic residue modulo p (so \left( \frac{5}{p} \right) = 1), then \rho_L(p) divides p-1, implying p divides L_n for some n dividing p-1. If instead \left( \frac{5}{p} \right) = -1, then \rho_L(p) divides p+1. Additionally, for any odd prime p, L_p \equiv 1 \pmod{p}.[29][33]Special Lucas Numbers
Lucas Primes
A Lucas prime is defined as a Lucas number L_n that is itself a prime number, where the Lucas sequence is given by L_0 = 2, L_1 = 1, and L_n = L_{n-1} + L_{n-2} for n \geq 2.[34] While L_p for prime p has been of particular interest due to potential algebraic factorizations for composite indices, Lucas primes more generally refer to any prime L_n regardless of whether n is prime.[35] The known small Lucas primes occur at specific indices n and provide examples of the sequence's primality patterns. These include:| Index n | Lucas Prime L_n |
|---|---|
| 0 | 2 |
| 2 | 3 |
| 4 | 7 |
| 5 | 11 |
| 7 | 29 |
| 8 | 47 |
| 11 | 199 |
| 13 | 521 |
| 16 | 2207 |
| 17 | 3571 |