Lehmer sequence
# Lehmer sequence

In mathematics, a Lehmer sequence is a generalization of a Lucas sequence.

## Algebraic relations

If a and b are complex numbers with

    $a+b={\sqrt {R}}$
    $ab=Q$

under the following conditions:

* Q and R are relatively prime nonzero integers
* $a/b$ is not a root of unity.

Then, the corresponding Lehmer numbers are:

    $U_{n}({\sqrt {R}},Q)={\frac {a^{n}-b^{n}}{a-b}}$

for n odd, and

    $U_{n}({\sqrt {R}},Q)={\frac {a^{n}-b^{n}}{a^{2}-b^{2}}}$

for n even.

Their companion numbers are:

    $V_{n}({\sqrt {R}},Q)={\frac {a^{n}+b^{n}}{a+b}}$

for n odd and

    $V_{n}({\sqrt {R}},Q)=a^{n}+b^{n}$

for n even.

## Recurrence

Lehmer numbers form a linear recurrence relation with

    $U_{n}=(R-2Q)U_{n-2}-Q^{2}U_{n-4}=(a^{2}+b^{2})U_{n-2}-a^{2}b^{2}U_{n-4}$

with initial values $U_{0}=0,\,U_{1}=1,\,U_{2}=1,\,U_{3}=R-Q=a^{2}+ab+b^{2}$. Similarly the companion sequence satisfies

    $V_{n}=(R-2Q)V_{n-2}-Q^{2}V_{n-4}=(a^{2}+b^{2})V_{n-2}-a^{2}b^{2}V_{n-4}$

with initial values $V_{0}=2,\,V_{1}=1,\,V_{2}=R-2Q=a^{2}+b^{2},\,V_{3}=R-3Q=a^{2}-ab+b^{2}.$

