A recurrence relation is an equation that describes a(n) in terms of one or more previous values in the sequence. Initial Conditions for the sequence are given values for a finite number of the terms of the sequence.
To solve a recurrence relation involving the sequence a0, a1, a2…… is to find an explicit formula for the general term a(n) as a function of n. A explicit formula allows to calculate the value of any term of the sequence without having to know the previous terms. Eg: Expansion
Recursion is a technique that solves a problem by solving a smaller problem of the same type.
Divide & Conquer: If problem is small, solve it directly, else: break into smaller sub-problems and solve each sub-problem recursively, combining the results into a solution for the whole problem.