In mathematics, the Lucas sequences U n ( P , Q ) {\displaystyle U_{n}(P,Q)} and V n ( P , Q ) {\displaystyle V_{n}(P,Q)} are certain constant-recursive integer sequences that satisfy the recurrence relation
x n = P ⋅ x n − 1 − Q ⋅ x n − 2 {\displaystyle x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2}}
where P {\displaystyle P} and Q {\displaystyle Q} are fixed integers. Although U n ( P , Q ) {\displaystyle U_{n}(P,Q)} and V n ( P , Q ) {\displaystyle V_{n}(P,Q)} satisfy the same recurrence relation, they differ on the values of their first two elements and thus differ for subsequent elements as well. Any sequence satisfying this recurrence relation can be represented as a linear combination of the Lucas sequences U n ( P , Q ) {\displaystyle U_{n}(P,Q)} and V n ( P , Q ) . {\displaystyle V_{n}(P,Q).}
More generally, Lucas sequences U n ( P , Q ) {\displaystyle U_{n}(P,Q)} and V n ( P , Q ) {\displaystyle V_{n}(P,Q)} represent sequences of polynomials in P {\displaystyle P} and Q {\displaystyle Q} with integer coefficients. Famous examples of Lucas sequences include the Fibonacci numbers, Mersenne numbers, Pell numbers, Lucas numbers, Jacobsthal numbers, and a superset of Fermat numbers (see below). Lucas sequences are named after the French mathematician Édouard Lucas.
Recurrence relations Given two integer parameters P {\displaystyle P} and Q {\displaystyle Q} , the Lucas sequences of the first kind U n ( P , Q ) {\displaystyle U_{n}(P,Q)} and of the second kind V n ( P , Q ) {\displaystyle V_{n}(P,Q)} are defined by the recurrence relations:
U 0 ( P , Q ) = 0 , U 1 ( P , Q ) = 1 , U n ( P , Q ) = P ⋅ U n − 1 ( P , Q ) − Q ⋅ U n − 2 ( P , Q ) for n > 1 , {\displaystyle {\begin{aligned}U_{0}(P,Q)&=0,\\U_{1}(P,Q)&=1,\\U_{n}(P,Q)&=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q){\mbox{ for }}n>1,\end{aligned}}}
and
… excerpt ends here. Continue reading the full article.
