We identify a type of recurrence that can be solved by special methods.
DEF: A recurrence relation
an = f (a0,...,an-1
has degree k if the function f depends on the term an-k and if it depends on no terms of lower index. It is linear of degree k if it has the form
am = c1an-1 + c2an-2+...+ ckan-k + g (n)
where each ck is a real function and ck = 0. It is homo genous if g (n) = 0
aExample 6.2.1: The recurrence system with intial condition
a0=0
and recurrence relation
an = an-1 + 2n - 1
is linear of degree one and non-homo geneous.