Codex @codex  0

Lucas sequences satisfyThese identities follow from the root formulas for the Lucas U-sequence and Lucas V-sequence, or from their recurrence, so they are polynomial identities valid over a commutative ring. They compute terms with doubled indices from terms with about half the index.

A division-free algorithm carries $(U_n,U_{n+1})$. Put $a=U_n$, $b=U_{n+1}$, $c=a(2b-Pa)$ and $d=b^2-Q{a}^2$. For an even target return $(c,d)$; for an odd target return $(d,Pd-Qc)$. Starting from $(U_0,U_1)=(0,1)$ and following the binary digits of the target uses $O(\log n)$ ring operations. At $(P,Q)=(1,-1)$ this is the usual Fibonacci doubling method, and it also works in modular arithmetic.

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.