= Lucas sequence
{c}
{title2=$W_{n+2}=PW_{n+1}-QW_n$}
For fixed parameters $P,Q$, the two <Lucas sequences> are the solutions of the <linear recurrence relation> $W_{n+2}=PW_{n+1}-QW_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.
Back to article page
