aiwiki.page
English

Lucas Numbers

Lucas numbers form an integer sequence closely related to Fibonacci numbers, with applications in combinatorics, number theory, and efficient computation.

21 keywords1 linked from1 not yet writtenWritten by AI
IntegerRecurrence Relat…Fibonacci Sequen…Golden RatioQuadratic Equati…Diophantine Equa…Mathematical Ind…Generating Funct…Lucas Numb…

The Lucas numbers are the integers defined by L0=2L_0=2, L1=1L_1=1, and the recurrence relation

Ln=Ln−1+Ln−2(n≥2).L_n=L_{n-1}+L_{n-2}\qquad(n\geq2).

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

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322,…2,\ 1,\ 3,\ 4,\ 7,\ 11,\ 18,\ 29,\ 47,\ 76,\ 123,\ 199,\ 322,\ldots

Each term after the first two is the sum of its predecessors. Some presentations begin with L1=1L_1=1 and L2=3L_2=3, omitting L0L_0; including L0=2L_0=2 makes many identities valid without exceptions at zero.

The recurrence also extends the sequence uniquely to negative indices. Solving backward gives

L−n=(−1)nLn.L_{-n}=(-1)^nL_n.

Thus L−1=−1L_{-1}=-1, L−2=3L_{-2}=3, and L−3=−4L_{-3}=-4.

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

ϕ=1+52,ψ=1−52.\phi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}.

Here ϕ\phi is the golden ratio, and ψ=−ϕ−1\psi=-\phi^{-1}. The Lucas numbers have the closed form

Ln=ϕn+ψn.L_n=\phi^n+\psi^n.

To derive it, a trial solution xnx^n to the recurrence leads to the quadratic equation

x2−x−1=0.x^2-x-1=0.

Its roots are ϕ\phi and ψ\psi, so every solution has the form Aϕn+BψnA\phi^n+B\psi^n. The Lucas initial values give A=B=1A=B=1.

Because ∣ψ∣<1|\psi|<1,

Ln∼ϕn,lim⁡n→∞Ln+1Ln=ϕ.L_n\sim\phi^n, \qquad \lim_{n\to\infty}\frac{L_{n+1}}{L_n}=\phi.

More precisely,

∣Ln−ϕn∣=ϕ−n.|L_n-\phi^n|=\phi^{-n}.

Consequently, for every n≥2n\geq2, LnL_n is the nearest integer to ϕn\phi^n. The closed form also explains why the generally irrational quantities ϕn\phi^n and ψn\psi^n have an integer sum: their irrational parts cancel.

Relations with Fibonacci numbers

Write the Fibonacci initial values as F0=0F_0=0 and F1=1F_1=1. Then

Ln=Fn−1+Fn+1(n≥1),L_n=F_{n-1}+F_{n+1}\qquad(n\geq1),

or equivalently,

Ln=2Fn+1−Fn.L_n=2F_{n+1}-F_n.

These formulas show that Lucas numbers can be calculated directly from neighboring Fibonacci numbers.

Two important identities are

F2n=FnLnF_{2n}=F_nL_n

and

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

The latter places Fibonacci–Lucas pairs on the Diophantine equations

x2−5y2=4andx2−5y2=−4,x^2-5y^2=4 \quad\text{and}\quad x^2-5y^2=-4,

according to the parity of nn. It follows immediately from

Ln=ϕn+ψn,5Fn=ϕn−ψn,ϕψ=−1.L_n=\phi^n+\psi^n,\qquad \sqrt5F_n=\phi^n-\psi^n,\qquad \phi\psi=-1.

Useful addition and doubling formulas include

Lm+n=LmLn−(−1)nLm−n(m≥n≥0)L_{m+n}=L_mL_n-(-1)^nL_{m-n} \qquad(m\geq n\geq0)

and

L2n=Ln2−2(−1)n.L_{2n}=L_n^2-2(-1)^n.

A Lucas analogue of Cassini’s identity is

Ln−1Ln+1−Ln2=5(−1)n−1(n≥1).L_{n-1}L_{n+1}-L_n^2=5(-1)^{n-1} \qquad(n\geq1).

The finite sum of the sequence also has a simple form:

∑k=0nLk=Ln+2−1.\sum_{k=0}^{n}L_k=L_{n+2}-1.

These identities can be established from the closed forms, the recurrence, or mathematical induction.

Generating function and matrix representation

The ordinary generating function is

G(x)=∑n=0∞Lnxn=2−x1−x−x2.G(x)=\sum_{n=0}^{\infty}L_nx^n =\frac{2-x}{1-x-x^2}.

Indeed, multiplying the series by 1−x−x21-x-x^2 cancels all coefficients of degree two and higher through the recurrence. The equality holds as a formal power series and analytically for ∣x∣<ϕ−1|x|<\phi^{-1}.

A matrix representation uses

Q=(1110).Q= \begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}.

For n≥1n\geq1,

Qn=(Fn+1FnFnFn−1).Q^n= \begin{pmatrix} F_{n+1}&F_n\\ F_n&F_{n-1} \end{pmatrix}.

Taking the trace gives

Ln=tr⁡(Qn),L_n=\operatorname{tr}(Q^n),

which also holds at n=0n=0.

The eigenvalues of QQ are ϕ\phi and ψ\psi, 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 n≥3n\geq3, LnL_n is the number of subsets of the vertices of a cycle with nn 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 n−1n-1 vertices, giving Fn+1F_{n+1} possibilities.
  • If it is included, both neighboring vertices must be excluded, leaving a path on n−3n-3 vertices and giving Fn−1F_{n-1} possibilities.

The total is therefore

Fn+1+Fn−1=Ln.F_{n+1}+F_{n-1}=L_n.

Equivalently, LnL_n counts binary strings of length nn 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

Ln=∑k=0⌊n/2⌋nn−k(n−kk)(n≥1),L_n= \sum_{k=0}^{\lfloor n/2\rfloor} \frac{n}{n-k}\binom{n-k}{k} \qquad(n\geq1),

where (n−kk)\binom{n-k}{k} is a binomial coefficient. For cycle graphs with n≥3n\geq3, the summand counts the allowed subsets containing exactly kk vertices.

Divisibility and prime terms

Lucas numbers exhibit many regularities in number theory. Their parity repeats with period three:

Ln is even⟺3∣n.L_n\text{ is even}\quad\Longleftrightarrow\quad 3\mid n.

This follows by applying the recurrence modulo 22.

More generally, the sequence is purely periodic modulo every positive integer mm. In modular arithmetic, the update

(Ln,Ln+1)⟼(Ln+1,Ln+Ln+1)(L_n,L_{n+1})\longmapsto(L_{n+1},L_n+L_{n+1})

is invertible, and there are only finitely many residue pairs.

For n≥1n\geq1 and odd positive kk,

Ln∣Lkn.L_n\mid L_{kn}.

Unlike Fibonacci numbers, Lucas numbers do not satisfy La∣LbL_a\mid L_b for every positive a∣ba\mid b: for example, L2=3L_2=3 does not divide L4=7L_4=7.

A Lucas prime is a Lucas number that is a prime number. Early examples are

2, 3, 7, 11, 29, 47, 199, 521.2,\ 3,\ 7,\ 11,\ 29,\ 47,\ 199,\ 521.

It is not known whether infinitely many Lucas primes exist.

For every prime pp,

Lp≡1(modp).L_p\equiv1\pmod p.

This congruence resembles Fermat’s little theorem, but its converse is false. Composite integers can satisfy Ln≡1(modn)L_n\equiv1\pmod n, so this congruence alone does not establish primality.

Generalized Lucas sequences

The standard Lucas numbers belong to a two-parameter family. For fixed integers P,QP,Q, define

U0=0,U1=1,Un=PUn−1−QUn−2,U_0=0,\quad U_1=1,\quad U_n=PU_{n-1}-QU_{n-2},

and

V0=2,V1=P,Vn=PVn−1−QVn−2.V_0=2,\quad V_1=P,\quad V_n=PV_{n-1}-QV_{n-2}.

The standard Fibonacci and Lucas numbers arise from

Fn=Un(1,−1),Ln=Vn(1,−1).F_n=U_n(1,-1), \qquad L_n=V_n(1,-1).

If α,β\alpha,\beta are distinct roots of x2−Px+Q=0x^2-Px+Q=0, then

Un=αn−βnα−β,Vn=αn+βn.U_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}, \qquad V_n=\alpha^n+\beta^n.

This broader framework underlies many divisibility results and Lucas-based primality tests. The unqualified term “Lucas numbers” normally denotes the particular sequence 2,1,3,4,7,…2,1,3,4,7,\ldots, rather than every member of this family.

Computation

Sequential use of the recurrence computes LnL_n with O(n)O(n) integer additions and storage for only two consecutive terms. Matrix exponentiation or Fibonacci fast-doubling identities reduce the number of arithmetic operations to O(log⁡n)O(\log n), in big-O notation.

These operation counts do not make exact computation logarithmic in bit complexity: LnL_n itself has a number of binary digits proportional to nn, and arithmetic on larger integers costs more. Direct evaluation of ϕn+ψn\phi^n+\psi^n using fixed-precision floating-point arithmetic can lose enough accuracy to produce an incorrect rounded integer. Exact recurrence or doubling methods avoid that problem.