Lucas sequence

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