RECURRENCE RELATIONS

This chapter presents the basic methods of solving linear recurrence re-

lations. Specically, after the introduction of the basic notions of linear re-

currence relations, the iteration method is employed to derive the solutions

of linear recurrence relations of the rst order. This recursive, step-by-step,

derivation of the solutions contributes to the understanding of the term re-

currence relation. Then, the method of characteristic roots for the solution

of linear recurrence relations with constant coeÆcients is presented. The

last section is devoted to the use of generating functions in solving linear

recurrence relations with constant or variable coeÆcients.