Lucas sequence

From Free net encyclopedia

In mathematics a Lucas sequence is a particular generalisation of the Fibonacci numbers and Lucas numbers. Lucas sequences were first studied by French mathematician Edouard Lucas.

Contents 1 Recurrence relations 2 Algebraic relations 3 Other relations 4 Specific names 5 Applications

Recurrence relations

Given two integer parameters P and Q which satisfy

<math>P^2 - 4Q \neq 0</math>

the Lucas sequences U(P,Q) and V(P,Q) are defined by the recurrence relations

<math>U_0(P,Q)=0</math>

<math>U_1(P,Q)=1</math>

<math>U_n(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q) \mbox{ for }n>1</math>

and

<math>V_0(P,Q)=2</math>

<math>V_1(P,Q)=P</math>

<math>V_n(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q) \mbox{ for }n>1</math>

Algebraic relations

If the roots of the characteristic equation

<math>x^2 - Px + Q=0</math>

are a and b then U(P,Q) and V(P,Q) can also be defined in terms of a and b by

<math>U_n(P,Q)= \frac{a^n-b^n}{a-b} = \frac{a^n-b^n}{ \sqrt{P^2-4Q}}</math>

<math>V_n(P,Q)=a^n+b^n</math>

from which we can derive the relations

<math>a^n = \frac{V_n + U_n \sqrt{P^2-4Q}}{2}</math>

<math>b^n = \frac{V_n - U_n \sqrt{P^2-4Q}}{2}.</math>

Note that a and b are distinct because <math>P^2-4Q</math> is not 0.

Other relations

The numbers in Lucas sequences satisfy relations that are analogues of the relations between Fibonacci numbers and Lucas numbers. For example :-

<math>U_n = \frac{V_{n+1} - Q V_{n-1}}{P^2-4Q}</math>

<math>V_n = U_{n+1} - Q U_{n-1}</math>

<math>U_{2n} = U_n V_n</math>

<math>V_{2n} = V_n^2 - 2Q^n</math>

<math>U_{n+m} = U_n U_{m+1} - Q U_m U_{n-1}</math>

<math>V_{n+m} = V_n V_m - Q^m V_{n-m}</math>.

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

U_n(1,−2) : Jacobsthal numbers

Applications

• LUC is a cryptosystem based on Lucas sequences.de:Lucas-Folge

fr:Suite_de_Lucas