Lucas sequence

In mathematics, a Lucas sequence is a particular generalisation of the Fibonacci numbers and Lucas numbers. Lucas sequences are named after French mathematician Edouard Lucas.

Recurrence relations

Given two integer parameters "P" and "Q" which satisfy

:$P^2\; -\; 4Q\; eq\; 0$

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)=Pcdot\; U\_\{n-1\}(P,Q)-Qcdot\; U\_\{n-2\}(P,Q)\; mbox\{\; for\; \}n>1\; ,$

and

:$V\_0(P,Q)=2\; ,$

:$V\_1(P,Q)=P\; ,$

:$V\_n(P,Q)=Pcdot\; V\_\{n-1\}(P,Q)-Qcdot\; V\_\{n-2\}(P,Q)\; mbox\{\; for\; \}n>1\; ,$

Algebraic relations

The characteristic equation of Lucas sequences is::$x^2\; -\; Px\; +\; Q=0\; ,$ It has the discriminant $D=P^2\; -\; 4Q$ and the roots::$a\; =\; frac\{P+sqrt\{D2quad\; ext\{and\}quad\; b\; =\; frac\{P-sqrt\{D2.\; ,$Note that "a" and "b" are distinct because $D\; e\; 0.$

The terms of Lucas sequences can be defined in terms of "a" and "b" as follows

:$U\_n(P,Q)=\; frac\{a^n-b^n\}\{a-b\}\; =\; frac\{a^n-b^n\}\{\; sqrt\{D$

:$V\_n(P,Q)=a^n+b^n\; ,$

from which one can derive the relations

:$a^n\; =\; frac\{V\_n\; +\; U\_n\; sqrt\{D\{2\}$

:$b^n\; =\; frac\{V\_n\; -\; U\_n\; sqrt\{D\{2\}$

(where the square root means its principal value).

Other relations

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

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.

References

*
*cite book | first=Paulo | last=Ribenboim | authorlink=Paulo Ribenboim | coauthors= | year=2000 | title=My Numbers, My Friends: Popular Lectures on Number Theory | edition= | publisher=Springer-Verlag | location=New York | id=0-387-98911-0 | pages=1-50
*cite book | title=Proofs that Really Count | author=Arthur T. Benjamin | coauthors=Jennifer J. Quinn | publisher=Mathematical Association of America | year=2003 | isbn=0883853337 | pages=35