Recurrence Relations

A recurrence relation is an equation in which a function is defined in terms of itself.

The Fibonacci numbers are described by the recurrence relation

$$F_n=F_{n-1}+F_{n-2}$$

with the initial values $F_0=0$ and $F_1=1$.

Any polynomial can be represented by a recurrence, such as the linear function:

$$a_n=a_{n-1}+1,a_1=1⟶a_n=n$$

Any exponential can be represented by a recurrence:

$$a_n=2a_{n-1},a_1=1⟶a_n=2^{n-1}$$

Functions that cannot be easily described using conventional notation can be represented naturally using recurrences, such as:

$$a_n=n{a}_{n-1},a_1=1⟶a_n=n!$$

The self-reference property of recurrence relations is shared with recursive programs or algorithms, as the shared roots of both terms reflect. Essentially, recurrence relations provide a way to analyze recursive structures, such as algorithms. Many divide-and-conquer algorithms have time complexities that are naturally modeled by recurrence relations. The ability to solve such recurrences is important to understanding when divide-and-conquer algorithms perform well, and provides an important tool for analysis in general.