This is an expository account of a constructive theorem on the shortest linear recurrences of a finite sequence over an arbitrary Integral domain R. A generalization of rational approximation, which we call "realization", plays a key role throughout the paper.
We also give the associated "minimal realization" algorithm, which has a simple control structure and is division-free- It is easy to show that the number of R-multiplications required is O(n^2), where n is the length of the input sequence.
Our approach is algebraic and independent of any particular application. We view a linear recurring sequence as a torsion clement in a natural R[X]-module. The standard R[X]-module of Laurent polynomials over R underlies our approach to finite sequences. The prerequisites are nominal and we use short Fibonacci sequences as running examples.