Next: The main theorem Up: Linear recursive sequences Previous: Characteristic polynomials

Ideals and minimal characteristic polynomials

The same sequence can satisfy many different linear recurrences. For example, doubling (5) shows the Fibonacci sequence also satisfies

which is a linear recurrence with characteristic polynomial . It also satisfies

and adding these two relations, we find that also satisfies

which has characteristic polynomial .

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 .
In general, a nonempty set of polynomials satisfying (a) and (b) is called an ideal.

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 monic if the coefficient of the highest power of is 1.)

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

but we also know that

and it is easy to show that cannot satisfy a linear recurrence of order less than 2, so is a linear recursive sequence of order 2, with minimal characteristic polynomial .

Next: The main theorem Up: Linear recursive sequences Previous: Characteristic polynomials
Zvezdelina Stankova-Frenkel 2000-09-20