# Recurrence relations

#### Convert recurrence relation to closed form⌗

- Use method of differences
- if $k^{th}$ order of differences are in A.P. then it is a polynomial of degree $k+1$.
- if $k^{th}$ order of differences are in G.P. with common ration $r$ and first term $a$, then $n^{th}$ term is $ar^n + bn^{k-1} + \cdots + c$.