The same sequence can satisfy many different linear recurrences. For example, doubling (5) shows the Fibonacci sequence also satisfies
Now consider an arbitrary sequence . Let be the set of characteristic polynomials of all linear recurrences satisfied by . Then
Fact from algebra: Let be an ideal of polynomials. Then either or else there is a unique monic polynomial such that
This fact, applied to the ideal of characteristic polynomials of a linear recursive sequence shows that there is always a minimal characteristic polynomial , which is the monic polynomial of lowest degree in . It is the characteristic polynomial of the lowest order non-trivial linear recurrence satisfied by . The characteristic polynomial of any other linear recurrence satisfied by is a polynomial multiple of .
The order of a linear recursive sequence is defined to be the lowest order among all (nontrivial) linear recurrences satisfied by . The order also equals the degree of the minimal characteristic polynomial. For example, as we showed above, satisfies