info prev up next book cdrom email home

Lucas Sequence

Let $P$, $Q$ be Positive Integers. The Roots of

\end{displaymath} (1)

$\displaystyle a$ $\textstyle \equiv$ $\displaystyle {\textstyle{1\over 2}}(P+\sqrt{D}\,)$ (2)
$\displaystyle b$ $\textstyle \equiv$ $\displaystyle {\textstyle{1\over 2}}(P-\sqrt{D}\,),$ (3)

D\equiv P^2-4Q,
\end{displaymath} (4)

$\displaystyle a+b$ $\textstyle =$ $\displaystyle P$ (5)
$\displaystyle ab$ $\textstyle =$ $\displaystyle {\textstyle{1\over 4}}(P^2-D)=Q$ (6)
$\displaystyle a-b$ $\textstyle =$ $\displaystyle \sqrt{D}.$ (7)

Then define
$\displaystyle U_n(P,Q)$ $\textstyle \equiv$ $\displaystyle {a^n-b^n\over a-b}$ (8)
$\displaystyle V_n(P,Q)$ $\textstyle \equiv$ $\displaystyle a^n+b^n.$ (9)

The first few values are therefore
$\displaystyle U_0(P,Q)$ $\textstyle =$ $\displaystyle 0$ (10)
$\displaystyle U_1(P,Q)$ $\textstyle =$ $\displaystyle 1$ (11)
$\displaystyle V_0(P,Q)$ $\textstyle =$ $\displaystyle 2$ (12)
$\displaystyle V_1(P,Q)$ $\textstyle =$ $\displaystyle P.$ (13)

The sequences
$\displaystyle U(P,Q)$ $\textstyle =$ $\displaystyle \{U_n(P,Q) : n\geq 1\}$ (14)
$\displaystyle V(P,Q)$ $\textstyle =$ $\displaystyle \{V_n(P,Q) : n\geq 1\}$ (15)

are called Lucas sequences, where the definition is usually extended to include
U_{-1} = {a^{-1}-b^{-1}\over a-b} = {-1\over ab} = -{1\over Q}.
\end{displaymath} (16)

For $(P,Q)=(1,-1)$, the $U_n$ are the Fibonacci Numbers and $V_n$ are the Lucas Numbers. For $(P,Q)=(2,-1)$, the Pell Numbers and Pell-Lucas numbers are obtained. $(P,Q)=(1,-2)$ produces the Jacobsthal Numbers and Pell-Jacobsthal Numbers.

The Lucas sequences satisfy the general Recurrence Relations

$\displaystyle U_{m+n}$ $\textstyle =$ $\displaystyle {a^{m+n}-b^{m+n}\over a-b}$  
  $\textstyle =$ $\displaystyle {(a^m-b^m)(a^n+b^n)\over a-b} - {a^nb^n(a^{m-n}-b^{m-n})\over a-b}$  
  $\textstyle =$ $\displaystyle U_mV_n-a^nb^nU_{m-n}$ (17)
$\displaystyle V_{m+n}$ $\textstyle =$ $\displaystyle a^{m+n}+b^{m+n}$  
  $\textstyle =$ $\displaystyle (a^m+b^m)(a^n+b^n)-a^nb^n(a^{m-n}+b^{m-n})$  
  $\textstyle =$ $\displaystyle V_mV_n-a^nb^nV_{m-n}.$ (18)

Taking $n=1$ then gives
$\displaystyle U_m(P,Q)$ $\textstyle =$ $\displaystyle PU_{m-1}(P,Q)-QU_{m-2}(P,Q)$ (19)
$\displaystyle V_m(P,Q)$ $\textstyle =$ $\displaystyle PV_{m-1}(P,Q)-QV_{m-2}(P,Q).$ (20)

Other identities include
$\displaystyle U_{2n}$ $\textstyle =$ $\displaystyle U_nV_n$ (21)
$\displaystyle U_{2n+1}$ $\textstyle =$ $\displaystyle U_{n+1}V_n-Q^n$ (22)
$\displaystyle V_{2n}$ $\textstyle =$ $\displaystyle {V_n}^2-2(ab)^n={V_n}^2-2Q^n$ (23)
$\displaystyle V_{2n+1}$ $\textstyle =$ $\displaystyle V_{n+1}V_n-PQ^n.$ (24)

These formulas allow calculations for large $n$ to be decomposed into a chain in which only four quantities must be kept track of at a time, and the number of steps needed is $\sim \lg n$. The chain is particularly simple if $n$ has many 2s in its factorization.

The $U$s in a Lucas sequence satisfy the Congruence

U_{p^{n-1}[p-(D/p)]}\equiv 0\ \left({{\rm mod\ } {p^n}}\right)
\end{displaymath} (25)

\mathop{\rm GCD}(2QcD,p)=1,
\end{displaymath} (26)

P^2-4Q^2=c^2 D.
\end{displaymath} (27)

This fact is used in the proof of the general Lucas-Lehmer Test.

See also Fibonacci Number, Jacobsthal Number, Lucas-Lehmer Test, Lucas Number, Lucas Polynomial Sequence, Pell Number, Recurrence Sequence, Sylvester Cyclotomic Number


Dickson, L. E. ``Recurring Series; Lucas' $u_n$, $v_n$.'' Ch. 17 in History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Chelsea, pp. 393-411, 1952.

Ribenboim, P. The Little Book of Big Primes. New York: Springer-Verlag, pp. 35-53, 1991.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein