Lucas sequence ($W_{n+2}=P{W}_{n+1}-Q{W}_n$)

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 V-sequence has $V_0(P,Q)=2$, $V_1(P,Q)=P$ and $V_{n+2}=P{V}_{n+1}-Q{V}_n$. Thus its first terms are $2,P,P^2-2Q,P^3-3PQ$. For $(P,Q)=(1,-1)$ these are the Lucas numbers $2,1,3,4,7,\dots$.

For roots $\alpha ,\beta$ of $t^2-Pt+Q$, one has $V_n={\alpha }^n+{\beta }^n$, including the repeated-root case. This gives $V_{2n}=V_n^2-2Q^n$ immediately. The identity $V_n=2U_{n+1}-P{U}_n$ relates it to the Lucas U-sequence without requiring division.

The Lucas U-sequence has $U_0(P,Q)=0$, $U_1(P,Q)=1$ and $U_{n+2}=P{U}_{n+1}-Q{U}_n$. Its first terms are $0,1,P,P^2-Q,P^3-2PQ$. At $(P,Q)=(1,-1)$ it is the Fibonacci sequence.

If the roots $\alpha ,\beta$ of its characteristic polynomial of a linear recurrence are distinct, $U_n=({\alpha }^n-{\beta }^n)/(\alpha -\beta )$. This identity follows by checking the two initial conditions and the linear recurrence relation. At a repeated root $\alpha =\beta$, the corresponding formula is $U_n=n{\alpha }^{n-1}$ for $n\ge 1$.

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.