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