Lucas sequence

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

x_n = P x_n−1 − Q x_n−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 U_n(P,Q) and V_n(P,Q).

More generally, Lucas sequences U_n(P,Q) and V_n(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 U_n(P,Q) and of the second kind V_n(P,Q) are defined by the recurrence relations:

$\begin{align} 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{align}$

and

$\begin{align} 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{align}$

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

$\begin{align} 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{align}$

The ordinary generating functions are

$\sum_{n\ge 0} U_n(P,Q)z^n = \frac{z}{1-Pz+Qz^2};$

$\sum_{n\ge 0} V_n(P,Q)z^n = \frac{2-Pz}{1-Pz+Qz^2}.$

Examples

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

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

$\begin{array}{r|l} \text{General case} & (P,Q) = (1,-1) \\ \hline (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} \end{array}$

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:

U_n(1,−1) : Fibonacci numbers

V_n(1,−1) : Lucas numbers

U_n(2,−1) : Pell numbers

V_n(2,−1) : Companion Pell numbers or Pell-Lucas numbers

U_n(1,−2) : Jacobsthal numbers

V_n(1,−2) : Jacobsthal-Lucas numbers

U_n(3, 2) : Mersenne numbers 2ⁿ − 1

V_n(3, 2) : Numbers of the form 2ⁿ + 1, which include the Fermat numbers (Yubuta 2001).

U_n(x,−1) : Fibonacci polynomials

V_n(x,−1) : Lucas polynomials

U_n(x+1, x) : Repunits base x

V_n(x+1, x) : xⁿ + 1

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	A214733
1	-1	A000045	A000032
1	1	A128834	A087204
1	2	A107920
2	-1	A000129	A002203
2	1	A001477
2	2	A009545	A007395
2	3	A088137
2	4	A088138
2	5	A045873
3	-5	A015523	A072263
3	-4	A015521	A201455
3	-3	A030195	A172012
3	-2	A007482	A206776
3	-1	A006190	A006497
3	1	A001906	A005248
3	2	A000225	A000051
3	5	A190959
4	-3	A015530	A080042
4	-2	A090017
4	-1	A001076	A014448
4	1	A001353	A003500
4	2	A007070	A056236
4	3	A003462	A034472
4	4	A001787
5	-3	A015536
5	-2	A015535
5	-1	A052918	A087130
5	1	A004254	A003501
5	4	A002450	A052539

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.

See also

• Somer–Lucas pseudoprime

Notes

1. John Brillhart; Derrick Henry Lehmer; John Selfridge (April 1975). "New Primality Criteria and Factorizations of 2^m ± 1". Mathematics of Computation 29 (130): 620–647. doi:10.1090/S0025-5718-1975-0384673-1.
2. 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.
3. D. Bleichenbacher, W. Bosma, A. K. Lenstra (1995). "Some Remarks on Lucas-Based Cryptosystems" (PDF). Lecture Notes in Computer Science 963: 386–396. doi:10.1007/3-540-44750-4_31.

References

• Lehmer, D. H. (1930). "An extended theory of Lucas' functions". Annals of Mathematics 31 (3): 419–448. Bibcode:1930AnMat..31..419L. doi:10.2307/1968235. JSTOR 1968235.
• Ward, Morgan (1954). "Prime divisors of second order recurring sequences". Duke Math. J. 21 (4): 607–614. doi:10.1215/S0012-7094-54-02163-8. MR 0064073.
• Somer, Lawrence (1980). "The divisibility properties of primary Lucas Recurrences with respect to primes" (PDF). Fibonacci Quarterly 18: 316.
• Lagarias, J. C. (1985). "The set of primes dividing Lucas Numbers has density 2/3". Pac. J. Math. 118 (2): 449–461. doi:10.2140/pjm.1985.118.449. MR 789184.
• Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics 126 (2nd ed.). Birkhäuser. pp. 107–121. ISBN 0-8176-3743-5.
• Ribenboim, Paulo; McDaniel, Wayne L. (1996). "The square terms in Lucas Sequences". J. Numb. Theory 58 (1): 104–123. doi:10.1006/jnth.1996.0068.
• Joye, M.; Quisquater, J.-J. (1996). "Efficient computation of full Lucas sequences" (PDF). El. Lett. 32 (6): 537–538. doi:10.1049/el:19960359.
• Ribenboim, Paulo (2000). My Numbers, My Friends: Popular Lectures on Number Theory. New York: Springer-Verlag. pp. 1–50. ISBN 0-387-98911-0.
• Luca, Florian (2000). "Perfect Fibonacci and Lucas numbers". Rend. Circ Matem. Palermo 49 (2): 313–318. doi:10.1007/BF02904236.
• Yabuta, M. (2001). "A simple proof of Carmichael's theorem on primitive divisors" (PDF). Fibonacci Quarterly 39: 439–443..
• Arthur T. Benjamin; Jennifer J. Quinn (2003). Proofs that Really Count. Mathematical Association of America. p. 35. ISBN 0-88385-333-7.
• Lucas sequence at Encyclopedia of Mathematics.
• Weisstein, Eric W., "Lucas Sequence", MathWorld.
• Wei Dai. "Lucas Sequences in Cryptography".