In mathematics, a Lehmer sequence U n ( R , Q ) {\displaystyle U_{n}({\sqrt {R}},Q)} or V n ( R , Q ) {\displaystyle V_{n}({\sqrt {R}},Q)} is a generalization of a Lucas sequence U n ( P , Q ) {\displaystyle U_{n}(P,Q)} or V n ( P , Q ) {\displaystyle V_{n}(P,Q)} , allowing the square root of an integer R in place of the integer P. To ensure that the value is always an integer, every other term of a Lehmer sequence is divided by √R compared to the corresponding Lucas sequence. That is, when R = P2 the Lehmer and Lucas sequences are related as:
P U 2 n ( P 2 , Q ) = U 2 n ( P , Q ) U 2 n + 1 ( P 2 , Q ) = U 2 n + 1 ( P , Q ) V 2 n ( P 2 , Q ) = V 2 n ( P , Q ) P V 2 n + 1 ( P 2 , Q ) = V 2 n + 1 ( P , Q ) {\displaystyle {\begin{aligned}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{aligned}}}
Algebraic relations If a and b are complex numbers with
a + b = R {\displaystyle a+b={\sqrt {R}}}
a b = Q {\displaystyle ab=Q}
under the following conditions:
Q and R are relatively prime nonzero integers
a / b {\displaystyle a/b} is not a root of unity. Then, the corresponding Lehmer numbers are:
U n ( R , Q ) = a n − b n a − b {\displaystyle U_{n}({\sqrt {R}},Q)={\frac {a^{n}-b^{n}}{a-b}}}
for n odd, and
U n ( R , Q ) = a n − b n a 2 − b 2 {\displaystyle U_{n}({\sqrt {R}},Q)={\frac {a^{n}-b^{n}}{a^{2}-b^{2}}}}
for n even. Their companion numbers are:
V n ( R , Q ) = a n + b n a + b {\displaystyle V_{n}({\sqrt {R}},Q)={\frac {a^{n}+b^{n}}{a+b}}}
for n odd and
V n ( R , Q ) = a n + b n {\displaystyle 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 {\displaystyle 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 + a b + b 2 {\displaystyle 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 − 2 Q ) V n − 2 − Q 2 V n − 4 = ( a 2 + b 2 ) V n − 2 − a 2 b 2 V n − 4 {\displaystyle 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 − 2 Q = a 2 + b 2 , V 3 = R − 3 Q = a 2 − a b + b 2 . {\displaystyle 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 √R are incorporated. For example,
U 2 n ( R , Q ) = R U 2 n − 1 ( R , Q ) − Q U 2 n − 2 ( R , Q ) U 2 n + 1 ( R , Q ) = R U 2 n ( R , Q ) − Q U 2 n − 1 ( R , Q ) V 2 n ( R , Q ) = R V 2 n − 1 ( R , Q ) − Q V 2 n − 2 ( R , Q ) V 2 n + 1 ( R , Q ) = R V 2 n ( R , Q ) − Q V 2 n − 1 ( R , Q ) {\displaystyle {\begin{aligned}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{aligned}}}
References