(As an aside: This question lies relatively upon the border between the realms of Computer Science and Mathematics, and thus may be appropriate for StackOverflow as well.)
I am in need of a method of computationally finding the $n$th number of a Lucas Sequence of the first kind.
Given integer parameters $P$ and $Q$, a Lucas Sequence of the first kind $U_n(P, Q)$is defined by the following recurrence relation:
$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)$ for $n > 1$
This naturally lends itself to a recursive process, however for large values of $n$, this tends to be particularly time intensive, and cannot be performed by a computer in any reasonable amount of time.
I managed to implement the process iteratively, which massively reduced the time required to calculate the $n$th value, but for large numbers, the process is still quite time consuming. This is due to the fact that both recursive and iterative algorithms require computing every value $U_0(P, Q), U_1(P, Q), ... ,U_{n-1}(P, Q)$ in order to obtain a value for $U_n(P, Q)$. This leads me to my question:
Is there a way of computing the $n$th number of a Lucas Sequence of the first kind (given parameters $P$ and $Q$) directly, without calculating each prior value in the sequence? A direct equation, if such a thing exists, could be computed in relatively trivial time.
Yes (assuming $P^2 \ne 4Q$), but it's unlikely to give any computational advantage:
$$U_n(P,Q) = \frac{a^n - b^n}{a - b}$$ where $$a = \frac{P+\sqrt{P^2 - 4Q}}{2}\\ b = \frac{P-\sqrt{P^2 - 4Q}}{2}.$$
(Koval's algorithm might be the fastest available.)