Editing Lucas sequence (section)

== Recurrence relations ==

Given two integer parameters <math>P</math> and <math>Q</math>, the Lucas sequences of the first kind <math>U_n(P,Q)</math> and of the second kind <math>V_n(P,Q)</math> are defined by the [[recurrence relation]]s:

:<math>\begin{align}
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{align}</math>

and

:<math>\begin{align}
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{align}</math>

It is not hard to show  that for <math>n>0</math>,

:<math>\begin{align}
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{align}</math>

The above relations can be stated in [[matrix (mathematics)|matrix]] form as follows:
: <math>\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},</math>
<br>
: <math>\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},</math>
<br>
: <math>\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}.</math>