Lucas sequence

From Citizendium, the Citizens' Compendium

Jump to: navigation, search

Main Article

Talk

Related Articles ^[?]

Bibliography ^[?]

External Links ^[?]

This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer.

[edit intro]

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 \ne 0$ .

There exist two kinds of Lucas sequences:

Sequences $\scriptstyle U(P,Q) = (U_n(P,Q))_{n \ge 0}$ with $\scriptstyle U_n(P,Q)=\frac{a^n-b^n}{a-b}$ ,
Sequences $\scriptstyle V(P,Q) = (V_n(P,Q))_{n \ge 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$ .

1 Properties
2 Recurrence relation
3 Fibonacci numbers and Lucas numbers
4 Lucas sequences and the prime numbers
5 Further reading

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 \ge 0}$ it holds that $\scriptstyle U_0 = 0\$ and $U_1 = 1$ .
For every sequence $\scriptstyle V(P,Q) = (V_n(P,Q))_{n \ge 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\ne 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 Dp\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 Dn\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.