Editing Lucas sequence (section)

== Properties ==

=== Generating functions ===

The ordinary [[generating function]]s are
:<math>
\sum_{n\ge 0} U_n(P,Q)z^n = \frac{z}{1-Pz+Qz^2};
</math>
:<math>
\sum_{n\ge 0} V_n(P,Q)z^n = \frac{2-Pz}{1-Pz+Qz^2}.
</math>

=== Pell equations ===

When <math>Q=\pm 1</math>, the Lucas sequences <math>U_n(P, Q)</math> and <math>V_n(P, Q)</math> satisfy certain [[Pell equation]]s:
:<math>V_n(P,1)^2 - D\cdot U_n(P,1)^2 = 4,</math>
:<math>V_n(P,-1)^2 - D\cdot U_n(P,-1)^2 = 4(-1)^n.</math>

=== Relations between sequences with different parameters ===

*For any number ''c'', the sequences <math>U_n(P', Q')</math> and <math>V_n(P', Q')</math> with
::<math> P' = P + 2c  </math>
::<math> Q' = cP + Q + c^2  </math>
:have the same discriminant as <math>U_n(P, Q)</math> and <math>V_n(P, Q)</math>: 
:: <math>P'^2 - 4Q' = (P+2c)^2 - 4(cP + Q + c^2) = P^2 - 4Q = D.</math>

*For any number ''c'', we also have
:: <math>U_n(cP,c^2Q) = c^{n-1}\cdot U_n(P,Q),</math>
:: <math>V_n(cP,c^2Q) = c^n\cdot V_n(P,Q).</math>

=== Other relations ===

The terms of Lucas sequences satisfy relations that are generalizations of those between [[Fibonacci number]]s <math>F_n=U_n(1,-1)</math> and [[Lucas number]]s <math>L_n=V_n(1,-1)</math>. For example:
:<math>
\begin{array}{r|l}
\text{General case} & (P,Q) = (1,-1), D = P^2 - 4Q = 5
\\
\hline
D U_n = {V_{n+1} - Q V_{n-1}}=2V_{n+1}-P V_n  & 5F_n = {L_{n+1} + L_{n-1}}=2L_{n+1} - L_{n} 
\\
V_n = U_{n+1} - Q U_{n-1}=2U_{n+1}-PU_n  & L_n = F_{n+1} + F_{n-1}=2F_{n+1}-F_n 
\\
U_{m+n} = U_n U_{m+1} - Q U_m U_{n-1} = U_mV_n-Q^nU_{m-n} & F_{m+n} = F_n F_{m+1} + F_m F_{n-1} =F_mL_n-(-1)^nF_{m-n}
\\
U_{2n} = U_n (U_{n+1} - QU_{n-1}) = U_n V_n  & F_{2n} = F_n (F_{n+1} + F_{n-1}) = F_n L_n 
\\
U_{2n+1} = U_{n+1}^2 - Q U_n^2 & F_{2n+1} = F_{n+1}^2 + F_n^2
\\
V_{m+n} = V_m V_n - Q^n V_{m-n} = D U_m U_n + Q^n V_{m-n} & L_{m+n} = L_m L_n - (-1)^n L_{m-n} = 5 F_m F_n + (-1)^n L_{m-n} 
\\
V_{2n} = V_n^2 - 2Q^n = D U_n^2 + 2Q^n & L_{2n} = L_n^2 - 2(-1)^n = 5 F_n^2 + 2(-1)^n
\\
U_{m+n} = \frac{U_mV_n+U_nV_m}{2} & F_{m+n} = \frac{F_mL_n+F_nL_m}{2} 
\\
V_{m+n}=\frac{V_mV_n+DU_mU_n}{2} & L_{m+n}=\frac{L_mL_n+5F_mF_n}{2} 
\\
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} 
\\
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}
</math>

=== Divisibility properties ===

Among the consequences is that <math>U_{km}(P,Q)</math> is a multiple of <math>U_m(P,Q)</math>, i.e., the sequence <math>(U_m(P,Q))_{m\ge1}</math>
is a [[divisibility sequence]]. This implies, in particular, that <math>U_n(P,Q)</math> can be [[prime number|prime]] only when ''n'' is prime.
Another consequence is an analog of [[exponentiation by squaring]] that allows fast computation of <math>U_n(P,Q)</math> for large values of ''n''. 
Moreover, if <math>\gcd(P,Q)=1</math>, then <math>(U_m(P,Q))_{m\ge1}</math> is a [[divisibility sequence|strong divisibility sequence]].

Other divisibility properties are as follows:<ref>For such relations and divisibility properties, see {{harv|Carmichael|1913}}, {{harv|Lehmer|1930}} or {{harv|Ribenboim|1996|loc=2.IV}}.</ref>
* If ''n'' is an [[parity (mathematics)|odd]] multiple of ''m'', then <math>V_m</math> divides <math>V_n</math>.
* Let ''N'' be an integer [[relatively prime]] to 2''Q''.  If the smallest positive integer ''r'' for which ''N'' divides <math>U_r</math> exists, then the set of ''n'' for which ''N'' divides <math>U_n</math> is exactly the set of multiples of ''r''.
* If ''P'' and ''Q'' are [[parity (mathematics)|even]], then <math>U_n, V_n</math> are always even except <math>U_1</math>.
* If ''P'' is odd and ''Q'' is even, then <math>U_n, V_n</math> are always odd for every <math>n > 0</math>.
* If ''P'' is even and ''Q'' is odd, then the [[parity (mathematics)|parity]] of <math>U_n</math> is the same as ''n'' and <math>V_n</math> is always even.
* If ''P'' and ''Q'' are odd, then <math>U_n, V_n</math> are even if and only if ''n'' is a multiple of 3.
* If ''p'' is an odd prime, then <math>U_p\equiv\left(\tfrac{D}{p}\right), V_p\equiv P\pmod{p}</math> (see [[Legendre symbol]]).
* If ''p'' is an odd prime which divides ''P'' and ''Q'', then ''p'' divides <math>U_n</math> for every <math>n>1</math>.
* If ''p'' is an odd prime which divides ''P'' but not ''Q'', then ''p'' divides <math>U_n</math> if and only if ''n'' is even.
* If ''p'' is an odd prime which divides ''Q''  but not ''P'', then ''p'' never divides <math>U_n</math> for any <math>n > 0</math>.
* If ''p'' is an odd prime which divides ''D'' but not ''PQ'', then ''p'' divides <math>U_n</math> if and only if ''p'' divides ''n''.
* If ''p'' is an odd prime which does not divide ''PQD'', then ''p'' divides <math>U_l</math>, where <math>l=p-\left(\tfrac{D}{p}\right)</math>.

The last fact generalizes [[Fermat's little theorem]].  These facts are used in the [[Lucas–Lehmer primality test]].
Like Fermat's little theorem, the [[converse (logic)|converse]] of the last fact holds often, but not always; there exist [[composite number]]s ''n'' relatively prime to ''D'' and dividing <math>U_l</math>, where <math>l=n-\left(\tfrac{D}{n}\right)</math>.  Such composite numbers are called [[Lucas pseudoprime]]s.

A [[prime factor]] of a term in a Lucas sequence which 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.<ref name=Yabuta>{{cite journal |last1=Yabuta |first1=M |title=A simple proof of Carmichael's theorem on primitive divisors |journal=Fibonacci Quarterly |date=2001 |volume=39 |issue=5 |pages=439–443 |doi=10.1080/00150517.2001.12428701 |url=http://www.fq.math.ca/Scanned/39-5/yabuta.pdf |access-date=4 October 2018}}</ref>  Indeed, [[Robert Daniel Carmichael|Carmichael]] (1913) showed that if ''D'' is positive and ''n'' is not 1, 2 or 6, then <math>U_n</math> has a primitive prime factor.  In the case ''D'' is negative, a deep result of Bilu, Hanrot, Voutier and Mignotte<ref>{{cite journal | first1=Yuri | last1=Bilu | first2=Guillaume | last2=Hanrot | first3=Paul M. | last3=Voutier | first4=Maurice | last4=Mignotte | title=Existence of primitive divisors of Lucas and Lehmer numbers | journal=J. Reine Angew. Math. | year=2001 | volume=2001 | issue=539 | pages=75–122 | mr=1863855 | doi=10.1515/crll.2001.080 | s2cid=122969549 | url=https://hal.inria.fr/inria-00072867/file/RR-3792.pdf }}
</ref> shows that if ''n'' > 30, then <math>U_n</math> has a primitive prime factor and determines all cases <math>U_n</math> has no primitive prime factor.