Recurrence Relation

Recurrence relation defines a sequence of values by giving one or more initial terms, together with an equation expressing each subsequent term in terms of earlier ones.

Fibonacci Sequence

The famous Fibonacci sequence $f_1,f_2,f_3,\dots$ is defined by a particularly simple recurrence relation:

The initial two terms of the Fibonacci sequence are defined as $f_1=1$ and $f_2=1$. All subsequent terms are defined by the equation $f_n=f_{n-1}+f_{n-2}$, for $n\ge 3$

Solving Recurrences

I know 3 main techniques to solve recurrence:

1. Substitution method
2. Recursion Tree Method
3. Master Theorem
4. Akra-Bazzi method (section 4.7 of the CLRS book)