Recurrence Relations

Recurrence relations are a mathematical sequence describing how a recurring algorithm divides/decreases the work done. Conventionally, $T(n)$ is used to denote the work done for input size $n$.

There are 2 ways to solve general recurrence relations to obtain a closed-form formula:

Smoothness Rule §

#todo FIND A REFERENCE!!

Iteration §

Iteration involves by building the relation from the bottom-up, by substituting small values of n.

For example: $a_n=a_{n-1}+3,a_0=2$ $a_1=a_0+3=2+3=5$ $a_2=a_1+3=a_0+3+3=2+3+3=8$ $a_3=a_2+3=a_1+3+3=a_0+3+3+3=2+3\ast 3=11$ $\dots a_n=2+3\ast n$

Solving a simple arithmetic recurrence relation

Solve the following recurrence relation:

$$T(n)=\{\begin{array}{ll}T(n-1)+4,& n>1\\ 1,& n=1\end{array}$$

By using iteration, we have: $T(1)=1$ $T(2)=T(1)+4=1+4$ $T(3)=T(2)+4=1+4+4$ $T(n)=1+{\sum }_{k=1}^{n-1}4$ $T(n)=1+4(n-1)=4n-3$

Solving with a recurrence relation with triangular numbers

Solve the following recurrence relation:

$$T(n)=\{\begin{array}{ll}T(n-1)+n,& n>1\\ 1,& n=1\end{array}$$

With iteration we have: $T(1)=1$ $T(2)=T(1)+2=1+2$ $T(3)=T(2)+3=1+2+3$ $T(4)=T(3)+4=1+2+3+4$ $T(n)={\sum }_{k=1}^{n}k$ This has a closed-form solution given by the triangular numbers $T(n)=\frac{n(n+1)}{2}$

A linear combination recurrence relation (?)

Solve the following recurrence relation:

$$T(n)=\{\begin{array}{ll}2T(n-1)+1,& n>1\\ 1,& n=1\end{array}$$

With iteration, we have: $T(1)=1$ $T(2)=2T(1)+1=2+1$ $T(3)=2T(2)+1=2(2+1)+1=4+2+1$ $T(4)=2T(3)+1=2(4+2+1)+1=8+4+2+1$ $T(n)={\sum }_{k=0}^{n-1}{2}^k=2^n-1$ This is a geometric series, whose closed form formula is given by:

Telescoping §

Telescoping involves rearranging the equation and cancelling out terms

For example:  $T_n=T_{n-1}+2,T_0=1$

$T_1-T_0=2$ $+\cancel{T_2}-\cancel{T_1}=2$ $+\cancel{T_3}-\cancel{T_2}=2$ $+\dots T_n-\cancel{T_{n-1}}=2$
$\to T_n-T_0=2n$ $\to T_n=1+2n$

In Computer Science §

Most recurrence relations that use divide-and-conquer as a design pattern can be solved with the Master Theorem.