View source for Lucas sequence

{{TEX|done}}
A [[recursive sequence]] of integers defined by two integer parameters.  Given integers $P$, $Q$ with $D =P^2 - 4Q \neq 0$, the Lucas sequences of the first kind, $U_n = U_n(P,Q)$ and of the second kind $V_n = V_n(P,Q)$ are the recursive sequences defined by the same linear recurrence relation
\begin{equation}\label{eq:1}
X_{n+1} = P.X_n - Q.X_{n-1}
\end{equation}
but with starting values $U_0 = 0$, $U_1 = 1$ and $V_0 = 2$, $V_1 = P$.

The characteristic equation of the recurrence relation is $X^2 = P.X - Q$ with roots $\alpha,\beta = (P \pm \sqrt{D})/2$.  In terms of $\alpha,\beta$ we have
$$
U_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}\ ,
$$
$$
V_n = \alpha^n + \beta^n \ ,
$$
so that
$$
\alpha^n,\beta^n = \frac{U_n \pm V_n\sqrt{D}}{2} \ .
$$

In the case $P=1$,$Q=1$ the [[Fibonacci numbers]] and [[Lucas numbers]] are the Lucas sequences of the first and second kind respectively.

The [[z-transform]] of a Lucas sequence $\sum_{n=0}^\infty X_n z^{-n}$ satisfying \eqref{eq:1} is a rational function with denominator $z^2 - Pz + Q$.  Indeed,
$$
\sum_{n=0}^\infty U_n z^{-n} = \frac{1}{\alpha-\beta}\left(\frac{z}{z-\alpha} - \frac{z}{z-\beta}\right) = \frac{z}{z^2 - Pz + Q} \ .
$$
$$
\sum_{n=0}^\infty V_n z^{-n} = \frac{z}{z-\alpha} + \frac{z}{z-\beta} = \frac{z(2z-P)}{z^2 - Pz + Q} \ .
$$

===Lehmer numbers===
The '''Lehmer numbers''' are a modified form of Lucas sequence of the first kind, defined in terms of $\alpha, \beta$ algebraic numbers with $\alpha\beta$ and $(\alpha+\beta)^2$ integers:
$$
W_n = \begin{cases}\frac{\alpha^n - \beta^n}{\alpha - \beta},&n\,\text{odd},\\ \frac{\alpha^n - \beta^n}{\alpha^2 - \beta^2},&n\,\text{even}.\end{cases}
$$

==References==
* Paulo Ribenboim, "My Numbers, My Friends: Popular Lectures on Number Theory". Springer-Verlag (2002) ISBN 0-387-98911-0.
* Arthur T. Benjamin; Jennifer J. Quinn, "Proofs that Really Count". Mathematical Association of America (2003) ISBN 0883853337.
*  Wladyslaw Narkiewicz, "Rational Number Theory in the 20th Century: From PNT to FLT", Springer Monographs in Mathematics, Springer (2011) ISBN 0857295322