4 edited tags
3 edited tags
2 this is specifically about sequences of numbers

# How to solve Solving or approximating recurrence relations? for sequences of numbers

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

Examples are

1. theThe 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. \qquad \begin{align} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+2} &= F_n + F_{n+1} \end{align}

3. theThe number of Dyck wordsDyck 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 MergesortThe 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}

\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 relevantsignificant subclass

as well as

• methods that yield precise solutions and
• suchmethods 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.

# How to solve recurrence relations?

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

# 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

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

1