Homogeneous recurrence relations

 

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.