Lehmer sequence

{{hatnote|"Lehmer number" redirects here. It can also refer to a hypothetical solution to Lehmer's totient problem.}}

In mathematics, a Lehmer sequence $U_n(\sqrt R, Q)$ or $V_n(\sqrt R, Q)$ is a generalization of a Lucas sequence $U_n(P, Q)$ or $V_n(P, Q)$ , allowing the square root of an integer R in place of the integer P.{{Cite web|last=Weisstein|first=Eric W.|title=Lehmer Number|url=https://mathworld.wolfram.com/LehmerNumber.html|access-date=2020-08-11|website=mathworld.wolfram.com|language=en}}

To ensure that the value is always an integer, every other term of a Lehmer sequence is divided by {{radic|R}} compared to the corresponding Lucas sequence. That is, when R = P² the Lehmer and Lucas sequences are related as:

: $\begin{align}
P\,U_{2n}(\sqrt{P^2},Q) &= U_{2n}(P,Q) & U_{2n+1}(\sqrt{P^2},Q) &= U_{2n+1}(P,Q) \\
V_{2n}(\sqrt{P^2},Q) &= V_{2n}(P,Q) & P\,V_{2n+1}(\sqrt{P^2},Q) &= V_{2n+1}(P,Q)
\end{align}$

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^2U_{n-4} = (a^2+b^2)U_{n-2}-a^2b^2U_{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^2V_{n-4} = (a^2+b^2)V_{n-2}-a^2b^2V_{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.$

All Lucas sequence recurrences apply to Lehmer sequences if they are divided into cases for even and odd n and appropriate factors of {{radic|R}} are incorporated. For example,

: $\begin{align}
U_{2n}(\sqrt R,Q) &= \phantom{R\,} U_{2n-1}(\sqrt R,Q) - Q\, U_{2n-2}(\sqrt R,Q) &
U_{2n+1}(\sqrt R,Q) &= R\, U_{2n}(\sqrt R,Q) - Q\, U_{2n-1}(\sqrt R,Q) \\
V_{2n}(\sqrt R,Q) &= R\, V_{2n-1}(\sqrt R,Q) - Q\, V_{2n-2}(\sqrt R,Q) &
V_{2n+1}(\sqrt R,Q) &= \phantom{R\,} V_{2n}(\sqrt R,Q) - Q\, V_{2n-1}(\sqrt R,Q)
\end{align}$

References

Category:Integer sequences