Ideals and minimal characteristic polynomials

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

- (a)
- If and then .
- (b)
- If and is any polynomial, then .

**Fact from algebra:**
Let be an ideal of polynomials.
Then either or else there is a unique monic polynomial
such that

the set of polynomial multiples of $f(x)$ is a polynomial

(A polynomial is

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