Ideals and minimal characteristic polynomials

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

$$2 F_{n+2} - 2 F_{n+1} - 2F_n = 0,$$

which is a linear recurrence with characteristic polynomial $2x^2-2x-2$. It also satisfies

$$F_{n+3} - F_{n+2} - F_{n+1} = 0,$$

and adding these two relations, we find that $\{F_n\}$ also satisfies

$$F_{n+3} + F_{n+2} - 3 F_{n+1} - 2 F_n = 0$$

which has characteristic polynomial $x^3+x^2-3x-2=(x+2)(x^2-x-1)$.

Now consider an arbitrary sequence $\{a_n\}$. Let $I$ be the set of characteristic polynomials of all linear recurrences satisfied by $\{a_n\}$. Then

(a)

If $f(x) \in I$ and $g(x) \in I$ then $f(x)+g(x) \in I$.

(b)

If $f(x) \in I$ and $h(x)$ is any polynomial, then $h(x) f(x) \in I$.

In general, a nonempty set $I$ of polynomials satisfying (a) and (b) is called an ideal.

Fact from algebra: Let $I$ be an ideal of polynomials. Then either $I=\{0\}$ or else there is a unique monic polynomial $f(x) \in I$ such that

$$I =$$   the set of polynomial multiples of $f(x)$$$= \{ h(x)f(x) \mid h(x)$$    is a polynomial$$\}.$$

(A polynomial is monic if the coefficient of the highest power of $x$ is 1.)

This fact, applied to the ideal of characteristic polynomials of a linear recursive sequence $\{a_n\}$ shows that there is always a minimal characteristic polynomial $f(x)$, which is the monic polynomial of lowest degree in $I$. It is the characteristic polynomial of the lowest order non-trivial linear recurrence satisfied by $\{a_n\}$. The characteristic polynomial of any other linear recurrence satisfied by $\{a_n\}$ is a polynomial multiple of $f(x)$.

The order of a linear recursive sequence $\{a_n\}$ is defined to be the lowest order among all (nontrivial) linear recurrences satisfied by $\{a_n\}$. The order also equals the degree of the minimal characteristic polynomial. For example, as we showed above, $\{F_n\}$ satisfies

$$F_{n+3} + F_{n+2} - 3 F_{n+1} - 2 F_n = 0,$$

but we also know that

$$F_{n+2}-F_{n+1}-F_n=0,$$

and it is easy to show that $\{F_n\}$ cannot satisfy a linear recurrence of order less than 2, so $\{F_n\}$ is a linear recursive sequence of order 2, with minimal characteristic polynomial $x^2-x-1$.