Lucas sequence

From Wikipedia, the free encyclopedia
Jump to: navigation, search
To be distinguished from 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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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 OEISA214733
1 -1 OEISA000045 OEISA000032
1 1 OEISA128834 OEISA087204
1 2 OEISA107920
2 -1 OEISA000129 OEISA002203
2 1 OEISA001477
2 2 OEISA009545 OEISA007395
2 3 OEISA088137
2 4 OEISA088138
2 5 OEISA045873
3 -5 OEISA015523 OEISA072263
3 -4 OEISA015521 OEISA201455
3 -3 OEISA030195 OEISA172012
3 -2 OEISA206776
3 -1 OEISA006190 OEISA006497
3 1 OEISA001906 OEISA005248
3 2 OEISA000225 OEISA000051
3 5 OEISA190959
4 -3 OEISA015530 OEISA080042
4 -2 OEISA090017
4 -1 OEISA001076 OEISA014448
4 1 OEISA001353 OEISA003500
4 2 OEISA056236
4 3 OEISA003462 OEISA034472
4 4 OEISA001787
5 -3 OEISA015536
5 -2 OEISA015535
5 -1 OEISA087130
5 1 OEISA003501
5 4 OEISA002450 OEISA052539

Applications[edit]

  • 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[edit]

  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. 

See also[edit]