TOPICS

Lucas Sequence

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Let P, Q be integers satisfying

D=P^2-4Q>0.
(1)

Then roots of

x^2-Px+Q=0
(2)

are

a=1/2(P+sqrt(D))
(3)
b=1/2(P-sqrt(D)),
(4)

so

a+b=P
(5)
ab=1/4(P^2-D)
(6)
=Q
(7)
a-b=sqrt(D).
(8)

Now define

U_n(P,Q)=(a^n-b^n)/(a-b)
(9)
V_n(P,Q)=a^n+b^n
(10)

for integer n>=0, so the first few values are

U_0=0
(11)
U_1=1
(12)
U_2=P
(13)
U_3=P^2-Q
(14)
U_4=P(P^2-2Q)
(15)
U_5=P^4-3QP^2+Q^2
(16)
U_6=P(P^2-3Q)(P^2-Q)
(17)
U_7=P^6-5QP^4+6Q^2P^2-Q^3
(18)
U_8=P(P^2-2Q)(P^4-4QP^2+2Q^2)
(19)
U_9=(P^2-Q)(P^6-6QP^4+9Q^2P^2-Q^3)
(20)
U_(10)=P(P^4-3QP^2+Q^2)(P^4-5QP^2+5Q^2)
(21)

and

V_0=2
(22)
V_1=P
(23)
V_2=P^2-2Q
(24)
V_3=P(P^2-3Q)
(25)
V_4=P^4-4QP^2+2Q^2
(26)
V_5=P(P^4-5QP^2+5Q^2)
(27)
V_6=(P^2-2Q)(P^4-4QP^2+Q^2)
(28)
V_7=P(P^6-7QP^4+14Q^2P^2-7Q^3)
(29)
V_8=P^8-8QP^6+20Q^2P^4-16Q^3P^2+2Q^4
(30)
V_9=P(P^2-3Q)(P^6-6QP^4+9Q^2P^2-3Q^3)
(31)
V_(10)=(P^2-2Q)(P^8-8QP^6+19Q^2P^4-12Q^3P^2+Q^4).
(32)

Closed forms for these are given by

U_n=2^(1-n)sum_(k=0)^(|_(n-1)/2_|)(n; 2k+1)P^(n-2k-1)(P^2-4Q)^k
(33)
V_n=2^(1-n)sum_(k=0)^(|_n/2_|)(n; 2k)P^(n-2k)(P^2-4Q)^k.
(34)

The sequences

U(P,Q)={U_n(P,Q):n>=1}
(35)
V(P,Q)={V_n(P,Q):n>=1}
(36)

are called Lucas sequences, where the definition is usually extended to include

U_(-1)=(a^(-1)-b^(-1))/(a-b)=(-1)/(ab)=-1/Q.
(37)

The following table summarizes special cases of U_n(P,Q) and V_n(P,Q).

(P,Q)U_nV_n
(1,-1)Fibonacci numbersLucas numbers
(2,-1)Pell numbersPell-Lucas numbers
(1,-2)Jacobsthal numbersPell-Jacobsthal numbers

The Lucas sequences satisfy the general recurrence relations

U_(m+n)=(a^(m+n)-b^(m+n))/(a-b)
(38)
=((a^m-b^m)(a^n+b^n))/(a-b)-(a^nb^n(a^(m-n)-b^(m-n)))/(a-b)
(39)
=U_mV_n-a^nb^nU_(m-n)
(40)
V_(m+n)=a^(m+n)+b^(m+n)
(41)
=(a^m+b^m)(a^n+b^n)-a^nb^n(a^(m-n)+b^(m-n))
(42)
=V_mV_n-a^nb^nV_(m-n).
(43)

Taking n=1 then gives

U_m(P,Q)=PU_(m-1)(P,Q)-QU_(m-2)(P,Q)
(44)
V_m(P,Q)=PV_(m-1)(P,Q)-QV_(m-2)(P,Q).
(45)

Other identities include

U_(2n)=U_nV_n
(46)
U_(2n+1)=U_(n+1)V_n-Q^n
(47)
V_(2n)=V_n^2-2(ab)^n
(48)
=V_n^2-2Q^n
(49)
V_(2n+1)=V_(n+1)V_n-PQ^n.
(50)

These formulas allow calculations for large n to be decomposed into a chain in which only four quantities must be kept track of at a time, and the number of steps needed is ∼lgn. The chain is particularly simple if n has many 2s in its factorization.

See also

Binet Forms, Fibonacci Number, Jacobsthal Number, Lucas-Lehmer Test, Lucas Number, Lucas Polynomial Sequence, Pell Number, Recursive Sequence, Sylvester Cyclotomic Number

Explore with Wolfram|Alpha

References

Dickson, L. E. "Recurring Series; Lucas' u_n, v_n." Ch. 17 in History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Dover, pp. 393-411, 2005.Ribenboim, P. The Little Book of Big Primes. New York: Springer-Verlag, pp. 35-53, 1991.

Referenced on Wolfram|Alpha

Lucas Sequence

Cite this as:

Weisstein, Eric W. "Lucas Sequence." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LucasSequence.html

Subject classifications