Lucas Sequence

Let , be Positive Integers. The Roots of

$\begin{displaymath} x^2-Px+Q=0 \end{displaymath}$

(1)

are

$\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)

where

$\begin{displaymath} 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

$\begin{displaymath} U_{-1} = {a^{-1}-b^{-1}\over a-b} = {-1\over ab} = -{1\over Q}. \end{displaymath}$

(16)

For , the are the Fibonacci Numbers and are the Lucas Numbers. For , the Pell Numbers and Pell-Lucas numbers are obtained. 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

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

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

has many 2s in its factorization.

The s in a Lucas sequence satisfy the Congruence