Certain constant-recursive integer sequences
In mathematics, the Lucas sequences
and
are certain constant-recursive integer sequences that satisfy the recurrence relation
![{\displaystyle x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2))](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f001cb3047032efac2b4bf6ed7b4d5a5d7ec065)
where
and
are fixed integers. Any sequence satisfying this recurrence relation can be represented as a linear combination of the Lucas sequences
and
More generally, Lucas sequences
and
represent sequences of polynomials in
and
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
and
, the Lucas sequences of the first kind
and of the second kind
are defined by the recurrence relations:
![{\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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39b8067dbb65782e6f6908f6f128b1e6c86185ba)
and
![{\displaystyle {\begin{aligned}V_{0}(P,Q)&=2,\\V_{1}(P,Q)&=P,\\V_{n}(P,Q)&=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q){\mbox{ for ))n>1.\end{aligned))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4558d7e27cf5c77c030303baf083e6b91542fc64)
It is not hard to show that for
,
![{\displaystyle {\begin{aligned}U_{n}(P,Q)&={\frac {P\cdot U_{n-1}(P,Q)+V_{n-1}(P,Q)}{2)),\\V_{n}(P,Q)&={\frac {(P^{2}-4Q)\cdot U_{n-1}(P,Q)+P\cdot V_{n-1}(P,Q)}{2)).\end{aligned))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38de939c7fd884bcdebc764e6dead95552a4669e)
The above relations can be stated in matrix form as follows:
![{\displaystyle {\begin{bmatrix}U_{n}(P,Q)\\U_{n+1}(P,Q)\end{bmatrix))={\begin{bmatrix}0&1\\-Q&P\end{bmatrix))\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\U_{n}(P,Q)\end{bmatrix)),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad9d8779bd84dbd4fee57e86e215008a07702cb9)
![{\displaystyle {\begin{bmatrix}V_{n}(P,Q)\\V_{n+1}(P,Q)\end{bmatrix))={\begin{bmatrix}0&1\\-Q&P\end{bmatrix))\cdot {\begin{bmatrix}V_{n-1}(P,Q)\\V_{n}(P,Q)\end{bmatrix)),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a4a3686290aa145d3736a67a5c703259f349e03)
![{\displaystyle {\begin{bmatrix}U_{n}(P,Q)\\V_{n}(P,Q)\end{bmatrix))={\begin{bmatrix}P/2&1/2\\(P^{2}-4Q)/2&P/2\end{bmatrix))\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\V_{n-1}(P,Q)\end{bmatrix)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47dcf73b6e25bfe75d0a072ceaced310f986274a)
Explicit expressions
The characteristic equation of the recurrence relation for Lucas sequences
and
is:
![{\displaystyle x^{2}-Px+Q=0\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee4c9d05c963f53aa52587cfbcc0a45fcc1c9650)
It has the discriminant
and the roots:
![{\displaystyle a={\frac {P+{\sqrt {D))}{2))\quad {\text{and))\quad b={\frac {P-{\sqrt {D))}{2)).\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af15de5e67e8eb3c2c381388ea7d92279551a97b)
Thus:
![{\displaystyle a+b=P\,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a38b49c0426736742e66f805b0648951607ce99)
![{\displaystyle ab={\frac {1}{4))(P^{2}-D)=Q\,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c254ed8edcadda83fce6dfe2d8882bc3b9ea761)
![{\displaystyle a-b={\sqrt {D))\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ffe2cbe60ffa734128337f4ac46950a466fe6d7)
Note that the sequence
and the sequence
also satisfy the recurrence relation. However these might not be integer sequences.
Distinct roots
When
, a and b are distinct and one quickly verifies that
![{\displaystyle a^{n}={\frac {V_{n}+U_{n}{\sqrt {D))}{2))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e54d235001ff706176add341e193f3d753c1c6f3)
![{\displaystyle b^{n}={\frac {V_{n}-U_{n}{\sqrt {D))}{2)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/786814d0d99fb98f6510a773949879d5c5f2e205)
It follows that the terms of Lucas sequences can be expressed in terms of a and b as follows
![{\displaystyle U_{n}={\frac {a^{n}-b^{n)){a-b))={\frac {a^{n}-b^{n)){\sqrt {D))))](https://wikimedia.org/api/rest_v1/media/math/render/svg/52df8cdb047ec38c4dd573e6598176f2f636b1b7)
![{\displaystyle V_{n}=a^{n}+b^{n}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10a06a80b8357f9eb3986899dbfc3dc2bd48aed4)
Repeated root
The case
occurs exactly when
for some integer S so that
. In this case one easily finds that
![{\displaystyle U_{n}(P,Q)=U_{n}(2S,S^{2})=nS^{n-1}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6b959f60c8c7c382e9520ad766f257ffcc75a73)
![{\displaystyle V_{n}(P,Q)=V_{n}(2S,S^{2})=2S^{n}.\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc40c1569fd7cd5d1c6c7fcde6f8035b25c75e03)
Properties
Generating functions
The ordinary generating functions are
![{\displaystyle \sum _{n\geq 0}U_{n}(P,Q)z^{n}={\frac {z}{1-Pz+Qz^{2))};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5225d218e300f47926bb01dd2cc16852664b27f)
![{\displaystyle \sum _{n\geq 0}V_{n}(P,Q)z^{n}={\frac {2-Pz}{1-Pz+Qz^{2))}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68704966d35020994e6e530da6c091039bb2f578)
Pell equations
When
, the Lucas sequences
and
satisfy certain Pell equations:
![{\displaystyle V_{n}(P,1)^{2}-D\cdot U_{n}(P,1)^{2}=4,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c8574371b65e83d93cc3dfa8047a0b1e4146c1e)
![{\displaystyle V_{2n}(P,-1)^{2}-D\cdot U_{2n}(P,-1)^{2}=4,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4b87afe71a76ac13e55d8ac32fa9e2ab01012cf)
![{\displaystyle V_{2n+1}(P,-1)^{2}-D\cdot U_{2n+1}(P,-1)^{2}=-4.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2ecd8e24d4a9fda3b556a87c6eb78de31b7919e)
Relations between sequences with different parameters
- For any number c, the sequences
and
with
![{\displaystyle P'=P+2c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e12d0d3999ee128167ef8e26c9cdbff52a54eedc)
![{\displaystyle Q'=cP+Q+c^{2))](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d74d94ef57a806519394b776d56e04b87bf57a3)
- have the same discriminant as
and
:
![{\displaystyle P'^{2}-4Q'=(P+2c)^{2}-4(cP+Q+c^{2})=P^{2}-4Q=D.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0628456a82fd6efdf772d38fd9f900979cafd3a)
- For any number c, we also have
![{\displaystyle U_{n}(cP,c^{2}Q)=c^{n-1}\cdot U_{n}(P,Q),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86d151659ceb328bdf2815915a9c9dc49d59fa89)
![{\displaystyle V_{n}(cP,c^{2}Q)=c^{n}\cdot V_{n}(P,Q).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c80045c50964cb133feb03d3b9bea2137769b56)
Other relations
The terms of Lucas sequences satisfy relations that are generalizations of those between Fibonacci numbers
and Lucas numbers
. For example:
![{\displaystyle {\begin{array}{r|l}{\text{General case))&(P,Q)=(1,-1)\\\hline (P^{2}-4Q)U_{n}={V_{n+1}-QV_{n-1))=2V_{n+1}-PV_{n}&5F_{n}={L_{n+1}+L_{n-1))=2L_{n+1}-L_{n}\\V_{n}=U_{n+1}-QU_{n-1}=2U_{n+1}-PU_{n}&L_{n}=F_{n+1}+F_{n-1}=2F_{n+1}-F_{n}\\U_{2n}=U_{n}V_{n}&F_{2n}=F_{n}L_{n}\\V_{2n}=V_{n}^{2}-2Q^{n}&L_{2n}=L_{n}^{2}-2(-1)^{n}\\U_{m+n}=U_{n}U_{m+1}-QU_{m}U_{n-1}={\frac {U_{m}V_{n}+U_{n}V_{m)){2))&F_{m+n}=F_{n}F_{m+1}+F_{m}F_{n-1}={\frac {F_{m}L_{n}+F_{n}L_{m)){2))\\V_{m+n}=V_{m}V_{n}-Q^{n}V_{m-n}=DU_{m}U_{n}+Q^{n}V_{m-n}&L_{m+n}=L_{m}L_{n}-(-1)^{n}L_{m-n}=5F_{m}F_{n}+(-1)^{n}L_{m-n}\\V_{n}^{2}-DU_{n}^{2}=4Q^{n}&L_{n}^{2}-5F_{n}^{2}=4(-1)^{n}\\U_{n}^{2}-U_{n-1}U_{n+1}=Q^{n-1}&F_{n}^{2}-F_{n-1}F_{n+1}=(-1)^{n-1}\\V_{n}^{2}-V_{n-1}V_{n+1}=DQ^{n-1}&L_{n}^{2}-L_{n-1}L_{n+1}=5(-1)^{n-1}\\DU_{n}=V_{n+1}-QV_{n-1}&F_{n}={\frac {L_{n+1}+L_{n-1)){5))\\V_{m+n}={\frac {V_{m}V_{n}+DU_{m}U_{n)){2))&L_{m+n}={\frac {L_{m}L_{n}+5F_{m}F_{n)){2))\\U_{m+n}=U_{m}V_{n}-Q^{n}U_{m-n}&F_{n+m}=F_{m}L_{n}-(-1)^{n}F_{m-n}\\2^{n-1}U_{n}={n \choose 1}P^{n-1}+{n \choose 3}P^{n-3}D+\cdots &2^{n-1}F_{n}={n \choose 1}+5{n \choose 3}+\cdots \\2^{n-1}V_{n}=P^{n}+{n \choose 2}P^{n-2}D+{n \choose 4}P^{n-4}D^{2}+\cdots &2^{n-1}L_{n}=1+5{n \choose 2}+5^{2}{n \choose 4}+\cdots \end{array))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/303ed9431e9a12fc8952c0f75ad6337f7a6e8562)
Divisibility properties
Among the consequences is that
is a multiple of
, i.e., the sequence
is a divisibility sequence. This implies, in particular, that
can be prime only when n is prime.
Another consequence is an analog of exponentiation by squaring that allows fast computation of
for large values of n.
Moreover, if
, then
is a strong divisibility sequence.
Other divisibility properties are as follows:[1]
- If
is odd, then
divides
.
- Let N be an integer relatively prime to 2Q. If the smallest positive integer r for which N divides
exists, then the set of n for which N divides
is exactly the set of multiples of r.
- If P and Q are even, then
are always even except
.
- If P is even and Q is odd, then the parity of
is the same as n and
is always even.
- If P is odd and Q is even, then
are always odd for
.
- If P and Q are odd, then
are even if and only if n is a multiple of 3.
- If p is an odd prime, then
(see Legendre symbol).
- If p is an odd prime and divides P and Q, then p divides
for every
.
- If p is an odd prime and divides P but not Q, then p divides
if and only if n is even.
- If p is an odd prime and divides not P but Q, then p never divides
for
.
- If p is an odd prime and divides not PQ but D, then p divides
if and only if p divides n.
- If p is an odd prime and does not divide PQD, then p divides
, where
.
The last fact generalizes Fermat's little theorem. These facts are used in the Lucas–Lehmer primality test.
The converse of the last fact does not hold, as the converse of Fermat's little theorem does not hold. There exists a composite n relatively prime to D and dividing
, where
. Such a composite is called a Lucas pseudoprime.
A prime factor of a term in a Lucas sequence that does not divide any earlier term in the sequence is called primitive.
Carmichael's theorem states that all but finitely many of the terms in a Lucas sequence have a primitive prime factor.[2] Indeed, Carmichael (1913) showed that if D is positive and n is not 1, 2 or 6, then
has a primitive prime factor. In the case D is negative, a deep result of Bilu, Hanrot, Voutier and Mignotte[3] shows that if n > 30, then
has a primitive prime factor and determines all cases
has no primitive prime factor.
Software
Sagemath implements
and
as lucas_number1()
and lucas_number2()
, respectively.[7]