It is assumed
throughout this subsection that the recurrence relations are linear with constant
coefficients.
Definitions:
A geometric
progression is a sequence
for which
, the common ratio.
The characteristic
equation for the kth-order
recurrence relation
,
, is the equation
. The characteristic roots are the roots
of this equation.
The sequences
,
, . . . ,
are linearly
dependent if there exist constants
, not all zero, such that
for all
. Otherwise, they are linearly independent.