# 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 integer sequences that satisfy the recurrence relation

xn = P xn−1Q xn−2

where P and Q are fixed integers. Any other 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:

$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, \,$

and

$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, \,$

It is not hard to show that for $n>0$,

$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}. \,$

## Examples

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

$n\,$ $U_n(P,Q)\,$ $V_n(P,Q)\,$
$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}\,$

## Algebraic relations

The characteristic equation of the recurrence relation for Lucas sequences $U_n(P,Q)$ and $V_n(P,Q)$ is:

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

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

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

Thus:

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

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

### Distinct roots

When $D\ne 0$, a and b are distinct and one quickly verifies that

$a^n = \frac{V_n + U_n \sqrt{D}}{2}$
$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

$U_n= \frac{a^n-b^n}{a-b} = \frac{a^n-b^n}{ \sqrt{D}}$
$V_n=a^n+b^n \,$

### Repeated root

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

$U_n(P,Q)=U_n(2S,S^2) = nS^{n-1}\,$
$V_n(P,Q)=V_n(2S,S^2)=2S^n\,$.

### Additional sequences having the same discriminant

If the Lucas sequences $U_n(P, Q)$ and $V_n(P, Q)$ have discriminant $D = P^2 - 4Q$, then the sequences based on $P_2$ and $Q_2$ where

$P_2 = P + 2$
$Q_2 = P + Q + 1$

have the same discriminant: $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 $F_n=U_n(1,-1)$ and Lucas numbers $L_n=V_n(1,-1)$. For example:

General P = 1, Q = -1
$(P^2-4Q) U_n = {V_{n+1} - Q V_{n-1}}=2V_{n+1}-P V_n \,$ $5F_n = {L_{n+1} + L_{n-1}}=2L_{n+1} - L_{n} \,$
$V_n = U_{n+1} - Q U_{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} - Q U_m U_{n-1}=\frac{U_nV_m+U_mV_n}{2} \,$ $F_{n+m} = F_n F_{m+1} + F_m F_{n-1}=\frac{F_nL_m+F_mL_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} \,$

Among the consequences is that $U_{km}(P,Q)$ is a multiple of $U_m(P,Q)$, i.e., the sequence $(U_m(P,Q))_{m\ge1}$ is a divisibility sequence. This implies, in particular, that $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 $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.

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

$P\,$ $Q\,$ $U_n(P,Q)\,$ $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

• LUC is a public-key cryptosystem based on Lucas sequences[1] 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.[2] 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.

## References

1. ^ P. J. Smith, M. J. J. Lennon (1993). "LUC: A new public key system". Proceedings of the Ninth IFIP Int. Symp. on Computer Security: 103–117.
2. ^ D. Bleichenbacher, W. Bosma, A. K. Lenstra (1995). "Some Remarks on Lucas-Based Cryptosystems". Lecture Notes in Computer Science 963: 386–396. doi:10.1007/3-540-44750-4_31.