Lucas sequence

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:

:"Un"(1,−1) : Fibonacci numbers

:"Vn"(1,−1) : Lucas numbers

:"Un"(2,−1) : Pell numbers

:"Un"(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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Lucas — may refer to several things.People bearing the surname Lucas*See Lucas (surname) *François Édouard Anatole Lucas, mathematician who studied Lucas numbers and the closely related Fibonacci numbers (both of which are examples of a Lucas sequence) * …   Wikipedia

  • Lucas number — The Lucas numbers are an integer sequence named after the mathematician François Édouard Anatole Lucas (1842 ndash;1891), who studied both that sequence and the closely related Fibonacci numbers (both are Lucas sequences). Like the Fibonacci… …   Wikipedia

  • Lucas-Lehmer-Riesel test — The Lucas Lehmer Riesel test is a primality test for numbers of the form N=k 2^n 1, with 2^n > k. The test was developed by Hans Riesel and it is based on the Lucas–Lehmer test for Mersenne numbers.The algorithmThe algorithm is very similar to… …   Wikipedia

  • Lucas pseudoprime — In number theory, the classes of Lucas pseudoprime and Fibonacci pseudoprime comprise sequences of composite integers that passes certain tests that all primes pass: in this case, criteria relative to some Lucas sequence.DefinitionGiven two… …   Wikipedia

  • Lucas-Folge — Unter der Lucas Folge versteht man zwei unterschiedliche Dinge: Einerseits die Folge der Lucas Zahlen 2, 1, 3, 4, 7, 11, 18, 29, … bei der jedes Folgenglied (ab dem dritten) die Summe der beiden vorhergehenden ist. Andererseits die beiden… …   Deutsch Wikipedia

  • Lucas–Lehmer test for Mersenne numbers — This article is about the Lucas–Lehmer test (LLT), that only applies to Mersenne numbers. There is also a Lucas Lehmer Riesel test for numbers of the form N=k 2^n 1, with 2^n > k, based on the LLT: see Lucas Lehmer Riesel test. There is also a… …   Wikipedia

  • Séquence de Fibonacci — Suite de Fibonacci La suite de Fibonacci est une suite d entiers très connue. Elle doit son nom à un mathématicien italien connu sous le nom de Leonardo Fibonacci qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci,… …   Wikipédia en Français

  • Lucas chain — In mathematics, a Lucas chain is a restricted type of addition chain, named for the French mathematician Edouard Lucas. It is a sequence : a 0, a 1, a 2, a 3, ...that satisfies: a 0=1, and :for each k > 0: a k = a i + a j , and either a i = a j… …   Wikipedia

  • Séquence (informatique) — Suite (mathématiques) Pour les articles homonymes, voir Suite. En mathématiques, une suite est une famille d éléments indexée par les entiers naturels. Une suite finie est une famille indexée par les entiers strictement positifs inférieurs ou… …   Wikipédia en Français

  • Séquence (mathématiques) — Suite (mathématiques) Pour les articles homonymes, voir Suite. En mathématiques, une suite est une famille d éléments indexée par les entiers naturels. Une suite finie est une famille indexée par les entiers strictement positifs inférieurs ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”