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.