Lucas sequence

Not to be confused with the sequence of Lucas numbers, which is a particular Lucas sequence.

In mathematics, the Lucas sequences Un(P,Q) and Vn(P,Q) are certain constant-recursive integer sequences that satisfy the recurrence relation

xn = P xn−1Q xn−2

where P and Q are fixed integers. Any sequence satisfying this recurrence relation can be represented as a linear combination of the Lucas sequences Un(P,Q) and Vn(P,Q).

More generally, Lucas sequences Un(P,Q) and Vn(P,Q) represent sequences of polynomials in P and Q with integer coefficients.

Famous examples of Lucas sequences include the Fibonacci numbers, Mersenne numbers, Pell numbers, Lucas numbers, Jacobsthal numbers, and a superset of Fermat numbers. Lucas sequences are named after the French mathematician Édouard Lucas.

Recurrence relations

Given two integer parameters P and Q, the Lucas sequences of the first kind Un(P,Q) and of the second kind Vn(P,Q) are defined by the recurrence relations:

{\displaystyle {\begin{aligned}U_{0}(P,Q)&=0,\\U_{1}(P,Q)&=1,\\U_{n}(P,Q)&=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q){\mbox{ for }}n>1,\end{aligned}}}

and

{\displaystyle {\begin{aligned}V_{0}(P,Q)&=2,\\V_{1}(P,Q)&=P,\\V_{n}(P,Q)&=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q){\mbox{ for }}n>1.\end{aligned}}}

It is not hard to show that for ${\displaystyle n>0}$,

{\displaystyle {\begin{aligned}U_{n}(P,Q)&={\frac {P\cdot U_{n-1}(P,Q)+V_{n-1}(P,Q)}{2}},\\V_{n}(P,Q)&={\frac {(P^{2}-4Q)\cdot U_{n-1}(P,Q)+P\cdot V_{n-1}(P,Q)}{2}}.\end{aligned}}}

The ordinary generating functions are

${\displaystyle \sum _{n\geq 0}U_{n}(P,Q)z^{n}={\frac {z}{1-Pz+Qz^{2}}};}$
${\displaystyle \sum _{n\geq 0}V_{n}(P,Q)z^{n}={\frac {2-Pz}{1-Pz+Qz^{2}}}.}$

Examples

Initial terms of Lucas sequences Un(P,Q) and Vn(P,Q) are given in the table:

${\displaystyle {\begin{array}{r|l|l}n&U_{n}(P,Q)&V_{n}(P,Q)\\\hline 0&0&2\\1&1&P\\2&P&{P}^{2}-2Q\\3&{P}^{2}-Q&{P}^{3}-3PQ\\4&{P}^{3}-2PQ&{P}^{4}-4{P}^{2}Q+2{Q}^{2}\\5&{P}^{4}-3{P}^{2}Q+{Q}^{2}&{P}^{5}-5{P}^{3}Q+5P{Q}^{2}\\6&{P}^{5}-4{P}^{3}Q+3P{Q}^{2}&{P}^{6}-6{P}^{4}Q+9{P}^{2}{Q}^{2}-2{Q}^{3}\end{array}}}$

Algebraic relations

The characteristic equation of the recurrence relation for Lucas sequences ${\displaystyle U_{n}(P,Q)}$ and ${\displaystyle V_{n}(P,Q)}$ is:

${\displaystyle x^{2}-Px+Q=0\,}$

It has the discriminant ${\displaystyle D=P^{2}-4Q}$ and the roots:

${\displaystyle a={\frac {P+{\sqrt {D}}}{2}}\quad {\text{and}}\quad b={\frac {P-{\sqrt {D}}}{2}}.\,}$

Thus:

${\displaystyle a+b=P\,,}$
${\displaystyle ab={\frac {1}{4}}(P^{2}-D)=Q\,,}$
${\displaystyle a-b={\sqrt {D}}\,.}$

Note that the sequence ${\displaystyle a^{n}}$ and the sequence ${\displaystyle b^{n}}$ also satisfy the recurrence relation. However these might not be integer sequences.

Distinct roots

When ${\displaystyle D\neq 0}$, a and b are distinct and one quickly verifies that

${\displaystyle a^{n}={\frac {V_{n}+U_{n}{\sqrt {D}}}{2}}}$
${\displaystyle b^{n}={\frac {V_{n}-U_{n}{\sqrt {D}}}{2}}}$.

It follows that the terms of Lucas sequences can be expressed in terms of a and b as follows

${\displaystyle U_{n}={\frac {a^{n}-b^{n}}{a-b}}={\frac {a^{n}-b^{n}}{\sqrt {D}}}}$
${\displaystyle V_{n}=a^{n}+b^{n}\,}$

Repeated root

The case ${\displaystyle D=0}$ occurs exactly when ${\displaystyle P=2S{\text{ and }}Q=S^{2}}$ for some integer S so that ${\displaystyle a=b=S}$. In this case one easily finds that

${\displaystyle U_{n}(P,Q)=U_{n}(2S,S^{2})=nS^{n-1}\,}$
${\displaystyle V_{n}(P,Q)=V_{n}(2S,S^{2})=2S^{n}\,}$.

Additional sequences having the same discriminant

If the Lucas sequences ${\displaystyle U_{n}(P,Q)}$ and ${\displaystyle V_{n}(P,Q)}$ have discriminant ${\displaystyle D=P^{2}-4Q}$, then the sequences based on ${\displaystyle P_{2}}$ and ${\displaystyle Q_{2}}$ where

${\displaystyle P_{2}=P+2}$
${\displaystyle Q_{2}=P+Q+1}$

have the same discriminant: ${\displaystyle P_{2}^{2}-4Q_{2}=(P+2)^{2}-4(P+Q+1)=P^{2}-4Q=D}$.

Other relations

The terms of Lucas sequences satisfy relations that are generalizations of those between Fibonacci numbers ${\displaystyle F_{n}=U_{n}(1,-1)}$ and Lucas numbers ${\displaystyle L_{n}=V_{n}(1,-1)}$. For example:

${\displaystyle {\begin{array}{r|l}{\text{General case}}&(P,Q)=(1,-1)\\\hline (P^{2}-4Q)U_{n}={V_{n+1}-QV_{n-1}}=2V_{n+1}-PV_{n}&5F_{n}={L_{n+1}+L_{n-1}}=2L_{n+1}-L_{n}\\V_{n}=U_{n+1}-QU_{n-1}=2U_{n+1}-PU_{n}&L_{n}=F_{n+1}+F_{n-1}=2F_{n+1}-F_{n}\\U_{2n}=U_{n}V_{n}&F_{2n}=F_{n}L_{n}\\V_{2n}=V_{n}^{2}-2Q^{n}&L_{2n}=L_{n}^{2}-2(-1)^{n}\\U_{n+m}=U_{n}U_{m+1}-QU_{m}U_{n-1}={\frac {U_{n}V_{m}+U_{m}V_{n}}{2}}&F_{n+m}=F_{n}F_{m+1}+F_{m}F_{n-1}={\frac {F_{n}L_{m}+F_{m}L_{n}}{2}}\\V_{n+m}=V_{n}V_{m}-Q^{m}V_{n-m}&L_{n+m}=L_{n}L_{m}-(-1)^{m}L_{n-m}\end{array}}}$

Among the consequences is that ${\displaystyle U_{km}(P,Q)}$ is a multiple of ${\displaystyle U_{m}(P,Q)}$, i.e., the sequence ${\displaystyle (U_{m}(P,Q))_{m\geq 1}}$ is a divisibility sequence. This implies, in particular, that ${\displaystyle U_{n}(P,Q)}$ can be prime only when n is prime. Another consequence is an analog of exponentiation by squaring that allows fast computation of ${\displaystyle U_{n}(P,Q)}$ for large values of n. These facts are used in the Lucas–Lehmer primality test.

Carmichael's theorem states that all but finitely many of the terms in a Lucas sequence have a prime factor that does not divide any earlier term in the sequence (Yubuta 2001).

Specific names

The Lucas sequences for some values of P and Q have specific names:

Un(1,−1) : Fibonacci numbers
Vn(1,−1) : Lucas numbers
Un(2,−1) : Pell numbers
Vn(2,−1) : Companion Pell numbers or Pell-Lucas numbers
Un(1,−2) : Jacobsthal numbers
Vn(1,−2) : Jacobsthal-Lucas numbers
Un(3, 2) : Mersenne numbers 2n − 1
Vn(3, 2) : Numbers of the form 2n + 1, which include the Fermat numbers (Yubuta 2001).
Un(x,−1) : Fibonacci polynomials
Vn(x,−1) : Lucas polynomials
Un(x+1, x) : Repunits base x
Vn(x+1, x) : xn + 1

Some Lucas sequences have entries in the On-Line Encyclopedia of Integer Sequences:

${\displaystyle P\,}$ ${\displaystyle Q\,}$ ${\displaystyle U_{n}(P,Q)\,}$ ${\displaystyle V_{n}(P,Q)\,}$
-1 3
1 -1
1 1
1 2
2 -1
2 1
2 2
2 3
2 4
2 5
3 -5
3 -4
3 -3
3 -2
3 -1
3 1
3 2
3 5
4 -3
4 -2
4 -1
4 1
4 2
4 3
4 4
5 -3
5 -2
5 -1
5 1
5 4

Applications

• Lucas sequences are used in probabilistic Lucas pseudoprime tests, which are part of the commonly used Baillie-PSW primality test.
• Lucas sequences are used in some primality proof methods, including the Lucas-Lehmer-Riesel test, and the N+1 and hybrid N-1/N+1 methods such as those in Brillhart-Lehmer-Selfridge 1975[1]
• LUC is a public-key cryptosystem based on Lucas sequences[2] that implements the analogs of ElGamal (LUCELG), Diffie-Hellman (LUCDIF), and RSA (LUCRSA). The encryption of the message in LUC is computed as a term of certain Lucas sequence, instead of using modular exponentiation as in RSA or Diffie-Hellman. However, a paper by Bleichenbacher et al.[3] shows that many of the supposed security advantages of LUC over cryptosystems based on modular exponentiation are either not present, or not as substantial as claimed.