The sequence is called the non-homogeneous part of the recurrence.
If for all then the recurrence is said to be homogeneous.
In this case if and are two solutions to the recurrence, and and are constants, then are also solutions.
If for all then the recurrence is called a linear recurrence with constant coefficients. Such a recurrence with for all and is said to be of finite order and the smallest such integer is called the order of the recurrence. If no such exists, the recurrence is said to be of infinite order.
For example, the Fibonacci sequence is a linear recurrence with constant coefficients and order 2.
Now suppose that satisfies a homogeneous linear recurrence of finite order . The polynomial is called the companion polynomial of . If we assume that the coefficients come from a field we can write
for some polynomials in where .
Now suppose further that all and
let be the largest value of the .
It follows that if then
for some constant .
(to be continued)
|Date of creation||2013-03-22 16:52:29|
|Last modified on||2013-03-22 16:52:29|
|Last modified by||Mathprof (13753)|