2018 | OriginalPaper | Chapter

# 8. Recurrence Relations

Published in:
The Discrete Math Workbook

## Abstract

Recurrence relation is the method of specifying the function f(n), \(n\in \mathbb {N}\), for which:

1.

values of the function f(n) for some subset are specified in an explicit form:

$$\begin{aligned} N_m=\{1,2,\dots , m\}\subset \mathbb {N} \end{aligned}$$

$$\begin{aligned} f(1)=a_1, \; f(2)=a_2,\; \dots , \; f(m)=a_m; \end{aligned}$$

2.

values of the function for the arguments \(k\in \mathbb {N}\setminus N_m\) are expressed by the values f(i), where \(i=1,2,\dots , k-1\), in accordance with a specified rule.

The function constructed in this way is called recursive or recursively defined, and it is the solution of the recurrence relation. The set of values of the function f(n) is also referred to as the recursive sequence.

Let the recursive sequence \(\{a_n\}\) be defined. The sequence \(\{a_n\}\) is called the finite history sequence, if each subsequent term of the sequence explicitly depends on some fixed number of previous terms. If \(a_n\) depends on all \(a_i\), \(1\leqslant i\leqslant n-1\), then it is referred to as the full history sequence.

When analyzing algorithms, one quite often has to study the recursively defined sequences. The main methods for analyzing the recurrence relations are considered:

1.

method of substitution;

2.

method based on the solution of a characteristic equation;

3.

method of generating functions.