Lehmer sequence

Template:Hatnote 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.^[1]

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

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

Algebraic relations

If a and b are complex numbers with

a + b = \sqrt{R}

a b = 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 - 2 Q) 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} + a b + b^{2}$ . Similarly the companion sequence satisfies

V_{n} = (R - 2 Q) 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 - 2 Q = a^{2} + b^{2}, V_{3} = R - 3 Q = a^{2} - a b + 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 Template:Radic are incorporated. For example,