Solving or approximating recurrence relations for sequences of numbers

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

-
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}$

-
The Fibonacci sequence:

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

-
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}$

-
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.

Converting Full History to Limited History

This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers. Consider, for example, the recurrence
$$
T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)
$$
which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the randomly chosen pivot.) For any integer $n$, the value of $T(n)$ depends on all $T(k)$ with $k<n$. Recurrences of this form are called full history recurrences.

To solve this recurrence, we can transform it into a limited history recurrence, where $T(n)$ depends on only a constant number of previous values. But first, it helps to simplify the recurrence a bit, to collect common terms and eliminate pesky fractions.
\begin{align*}
n T(n) &= n^2 + 2\sum_{k=1}^{n-1} T(k)
\end{align*}
Now to convert to a limited-history recurrence, we write down the recurrence for $T(n-1)$, subtract, and regather terms:
\begin{align*}
(n-1) T(n-1) &= (n-1)^2 + 2\sum_{k=1}^{n-2} T(k)
\\
\implies
nT(n) - (n-1)T(n-1) &= (2n-1) + 2T(n-1)
\\[1ex]
\implies
n T(n) &= (2n-1) + (n+1) T(n-1)
\\[1ex]
\implies
\frac{T(n)}{n+1} &= \frac{2n-1}{n(n+1)} + \frac{T(n-1)}{n}
\end{align*}

Now if we define $t(n) = T(n)/(n+1)$ and replace the fraction $\frac{2n-1}{n(n+1)}$ with the simpler asymptotic form $\Theta(1/n)$, we obtain the much simpler recurrence
$$
t(n) = \Theta(1/n) + t(n-1).
$$
Expanding this recurrence into a summation immediately gives us $t(n) = \Theta(H_n) = \Theta(\log n)$, where $H_n$ is the $n$th harmonic number. We conclude that $\boldsymbol{T(n) = \Theta(n\log n)}$.

StackExchange Computer Science Q#2789, answer score: 35