Next: Example: solving a linear Up: Linear recursive sequences Previous: Ideals and minimal characteristic

# The main theorem

Theorem 1   Let be a polynomial with and . Factor over the complex numbers as

where are distinct nonzero complex numbers, and are positive integers. Then a sequence satisfies the linear recurrence with characteristic polynomial if and only if there exist polynomials , , ..., with for such that

for all $n$

Here is an important special case.

Corollary 2   Suppose in addition that has no repeated factors; in other words suppose that . Then where are distinct nonzero complex numbers (the roots of ). Then satisfies the linear recurrence with characteristic polynomial if and only if there exist constants (not depending on ) such that

for all $n$

Zvezdelina Stankova-Frenkel 2000-09-20