 Lucas sequence

For fixed parameters $P,Q$, the two Lucas sequences are the solutions of the linear recurrence relation $W_{n+2}=P{W}_{n+1}-Q{W}_n$ with initial values $U_0=0,U_1=1$ and $V_0=2,V_1=P$. They are the Lucas U-sequence and the Lucas V-sequence. The choice $(P,Q)=(1,-1)$ gives the Fibonacci sequence and the ordinary Lucas numbers.

If $\alpha ,\beta$ are distinct roots of $t^2-Pt+Q$, direct substitution gives $U_n=({\alpha }^n-{\beta }^n)/(\alpha -\beta )$ and $V_n={\alpha }^n+{\beta }^n$. The recurrence itself remains meaningful when the roots coincide or division is unavailable, so it is the safest definition over a general ring. Fast doubling for Lucas sequences exploits these two related solutions to compute distant terms.

The Lucas sequence is a series of numbers that is similar to the Fibonacci sequence.