Lucas sequence

From Wikipedia, the free encyclopedia

Not to be confused with the Lucas numbers, which are one Lucas sequence.

In mathematics, the Lucas sequences U_n(P,Q) and V_n(P,Q) are integer sequences that satisfy the recurrence relation x_n = Px_n-1 - Qx_n-2 where P and Q are integers. Given integers P and Q, the recurrence relation together with initial values x₀ and x₁ defines a unique sequence which is a linear combination of the Lucas sequences U_n(P,Q) and V_n(P,Q) defined below.

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

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

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

Hence U_n and V_n each satisfies the recurrence relation

$x_n = P x_{n-1} - Q x_{n-2}\, ,$

and the most general solution to this recurrence relation is

$x_n = s U_n + t V_n \, ,$

where s and t are constants which are defined uniquely by the initial values x₀ and x₁ as follows:

$x_0 = sU_0 + tV_0 = 2t \, \Rightarrow \, t = \frac{x_0}{2} \, ,$

$x_1 = sU_1 + tV_1 = s + Pt \, \Rightarrow \, s = x_1 - Pt = x_1 - P\frac{x_0}{2} \, .$

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

$U_n=\frac{P\cdot U_{n-1}+ V_{n-1}}{2} \, ,$

$V_n=\frac{(P^2-4Q)\cdot U_{n-1}+P\cdot V_{n-1}}{2} \, .$

$n\,$	$U_n\,$	$V_n\,$
$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}\,$

[edit] Algebraic relations

The characteristic equation of the recurrence relation

$x_n = P x_{n-1} - Q x_{n-2} \,$ is:

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

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

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

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

[edit] 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 \,$

[edit] Repeated root

The case $D = 0$ occurs exactly when $P = 2 S 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\,$ .

[edit] Other relations

The numbers in Lucas sequences satisfy relations that are generalisations of the relations between Fibonacci numbers and Lucas numbers. 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 \,$	$5U_n = {V_{n+1} + V_{n-1}}=2V_{n+1} - V_{n} \,$
$V_n = U_{n+1} - Q U_{n-1}=2U_{n+1}-PU_n \,$	$V_n = U_{n+1} + U_{n-1}=2U_{n+1}-U_n \,$
$U_{2n} = U_n V_n \,$	$U_{2n} = U_n V_n \,$
$V_{2n} = V_n^2 - 2Q^n \,$	$V_{2n} = V_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} \,$	$U_{n+m} = U_n U_{m+1} + U_m U_{n-1}=\frac{U_nV_m+U_mV_n}{2} \,$
$V_{n+m} = V_n V_m - Q^m V_{n-m} \,$	$V_{n+m} = V_n V_m - (-1)^m V_{n-m} \,$

Among the consequences is that $U k m$ is a multiple of $U m$ so that $U n$ can only be prime in case $n$ is.

Another is that fast computation of $U n$ for large values of $n$ is possible using a kind of Exponentiation by squaring.

These two facts together allow the Lucas-Lehmer primality test.

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

[edit] Applications

LUC is a cryptosystem based on Lucas sequences.

[edit] References

Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. 126 (2nd ed ed.). Birkhäuser. pp. 107–121. ISBN 0-8176-3743-5.
Ribenboim, Paulo (2000). My Numbers, My Friends: Popular Lectures on Number Theory. New York: Springer-Verlag. pp. 1–50. ISBN 0-387-98911-0.
Arthur T. Benjamin; Jennifer J. Quinn (2003). Proofs that Really Count. Mathematical Association of America. pp. 35. ISBN 0883853337.
Weistein, Eric W., "Lucas Sequence" from MathWorld.

Lucas sequence

From Wikipedia, the free encyclopedia

Contents

[edit] Recurrence relations

[edit] Algebraic relations

[edit] Distinct roots

[edit] Repeated root

[edit] Other relations

[edit] Specific names

[edit] Applications

[edit] References

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages