An Efficient Formula for Linear Recurrences
Charles M. Fiduccia · SIAM Journal on Computing · 1985
The solutions to a scalar, homogeneous, constant-coefficient, linear recurrence are expressible in terms of the powers of a companion matrix. We show how to compute these powers efficiently via polynomial multiplication. The result is a simple expression for the solution, which does not involve the characteristic roots and which is valid for any module over any commutative ring. The formula yields the nth term of the solution to a kth order recurrence with $O(\mu (k) \cdot \log n)$ arithmetic operations, where $\mu (k)$ is the total number of arithmetic operations required to multiply two polynomials of degree $k - 1$. Thus if the ring supports a fast Fourier transform, then $O(k \cdot \log k \cdot \log n)$ operations are sufficient to compute the nth term.