In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested mainly in the sequence's asymptotic growth.

Examples are

1. the runtime of a tail-recursive function stepping downwards to $0$ from $n$ whose body takes time $f(n)$

$\qquad \begin{align} T(0) &= 0 \\ T(n+1) &= T(n) + f(n) \end{align}$

2. the Fibonacci sequence

$\qquad \begin{align} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+2} &= F_n + F_{n+1} \end{align}$

3. the number of Dyck words with $n$ parenthesis pairs

$\qquad\begin{align} C_0 &= 1 \\ C_{n+1}&=\sum_{i=0}^{n}C_i\,C_{n-i} \end{align}$

and

4. the Mergesort runtime recurrence on lists of length $n$

$\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1 \end{align}$

What are methods to solve recurrence relations? We are looking for

• general methods and
• methods for a relevant subclass

as well as

• methods that yield precise solutions and
• such that provide (bounds on) asymptotic growth.

^{This is supposed to become a reference question. Please post one answer per method and provide a general description as well as an illustrative example.}

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested mainly in the sequence's asymptotic growth.

Examples are

1. The runtime of a tail-recursive function stepping downwards to $0$ from $n$ whose body takes time $f(n)$:

$\qquad \begin{align} T(0) &= 0 \\ T(n+1) &= T(n) + f(n) \end{align}$

2. The Fibonacci sequence:

$\qquad \begin{align} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+2} &= F_n + F_{n+1} \end{align}$

3. The number of Dyck words with $n$ parenthesis pairs:

$\qquad\begin{align} C_0 &= 1 \\ C_{n+1}&=\sum_{i=0}^{n}C_i\,C_{n-i} \end{align}$

4. The mergesort runtime recurrence on lists of length $n$:

$\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1 \end{align}$

What are methods to solve recurrence relations? We are looking for

• general methods and
• methods for a significant subclass

as well as

• methods that yield precise solutions and
• methods that provide (bounds on) asymptotic growth.

^{This is supposed to become a reference question. Please post one answer per method and provide a general description as well as an illustrative example.}