Lucas sequence

In mathematics, a Lucas sequence is a particular generalisation of sequences like the Fibonacci numbers, Lucas numbers, Pell numbers or Jacobsthal numbers. Lucas sequences have one common characteristic: they can be generated over quadratic equations of the form: $\scriptstyle x^{2}-Px+Q=0\$ with $\scriptstyle P^{2}-4Q\neq 0$.

There exist two kinds of Lucas sequences:

• Sequences $\scriptstyle U(P,Q)=(U_{n}(P,Q))_{n\geq 0}$ with $\scriptstyle U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}$,
• Sequences $\scriptstyle V(P,Q)=(V_{n}(P,Q))_{n\geq 0}$ with $\scriptstyle V_{n}(P,Q)=a^{n}+b^{n}\$,

where $\scriptstyle a\$ and $b\$ are the solutions

$a={\frac {P+{\sqrt {P^{2}-4Q}}}{2}}$

and

$b={\frac {P-{\sqrt {P^{2}-4Q}}}{2}}$

of the quadratic equation $\scriptstyle x^{2}-Px+Q=0$.

Properties

• The variables $\scriptstyle a\$ and $\scriptstyle b\$, and the parameter $\scriptstyle P\$ and $\scriptstyle Q\$ are interdependent. In particular, $\scriptstyle P=a+b\$ and $\scriptstyle Q=a\cdot b.$.
• For every sequence $\scriptstyle U(P,Q)=(U_{n}(P,Q))_{n\geq 0}$ it holds that $\scriptstyle U_{0}=0\$ and $U_{1}=1$.
• For every sequence $\scriptstyle V(P,Q)=(V_{n}(P,Q))_{n\geq 0}$ is holds that $\scriptstyle V_{0}=2\$ and $V_{1}=P$.

For every Lucas sequence the following are true:

• $\scriptstyle U_{2n}=U_{n}\cdot V_{n}\$
• $\scriptstyle V_{n}=U_{n+1}-QU_{n-1}\$
• $\scriptstyle V_{2n}=V_{n}^{2}-2Q^{n}\$
• $\scriptstyle \operatorname {gcd} (U_{m},U_{n})=U_{\operatorname {gcd} (m,n)}$
• $\scriptstyle m\mid n\implies U_{m}\mid U_{n}$ for all $\scriptstyle U_{m}\neq 1$

Recurrence relation

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

$U_{0}(P,Q)=0\,$

$U_{1}(P,Q)=1\,$

$U_{n}(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q){\mbox{ for }}n>1\,$

and

$V_{0}(P,Q)=2\,$

$V_{1}(P,Q)=P\,$

$V_{n}(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q){\mbox{ for }}n>1\,$

Fibonacci numbers and Lucas numbers

The two best known Lucas sequences are the Fibonacci numbers $\scriptstyle U(1,-1)\$ and the Lucas numbers $\scriptstyle V(1,-1)\$ with $\scriptstyle a={\frac {1+{\sqrt {5}}}{2}}$ and $\scriptstyle b={\frac {1-{\sqrt {5}}}{2}}$.

Lucas sequences and the prime numbers

If the natural number $\scriptstyle p\$ is a prime number then it holds that

• $\scriptstyle p\$ divides $\scriptstyle U_{p}(P,Q)-\left({\frac {D}{p}}\right)$
• $\scriptstyle p\$ divides $\scriptstyle V_{p}(P,Q)-P\$

Fermat's Little Theorem can then be seen as a special case of $\scriptstyle p\$ divides $\scriptstyle (V_{n}(P,Q)-P)\$ because $\scriptstyle a^{p}\equiv a{\pmod {p}}$ is equivalent to $\scriptstyle V_{p}(a+1,a)\equiv V_{1}(a+1,a){\pmod {p}}$.

The converse pair of statements that if $\scriptstyle n\$ divides $\scriptstyle U_{n}(P,Q)-\left({\frac {D}{n}}\right)$ then is $\scriptstyle n\$ a prime number and if $m\$ divides $\scriptstyle V_{m}(P,Q)-P\$ then is $m\$ a prime number) are individually false and lead to Fibonacci pseudoprimes and Lucas pseudoprimes, respectively.

Further reading

• P. Ribenboim, The New Book of Prime Number Records (3 ed.), Springer, 1996, ISBN 0-387-94457-5.
• P. Ribenboim, My Numbers, My Friends, Springer, 2000, ISBN 0-387-98911-0.