# How to convert a recurrence relation to a non recursive function

How does one convert a recurrence relation to a non-recursive function?

I am not sure about the substitution, recursion tree, and master method. Is there an easy way to do this?

-
For some recurrence relations this is very easy; for some it is very hard. What recurrence are you interested in, and what havce you tried? – Michael Lugo Mar 24 '11 at 22:18
Just to give a general idea, you may want to check out Wilf's Generatingfunctionology at math.upenn.edu/~wilf/DownldGF.html. Are you talking about the master theorom in computer science, by any chance? – Matt Groff Mar 24 '11 at 22:48
If you are referring to the methods in this MIT lecture and notes then the way to learn (as with most algorithms) is practice, initially following the book or notes. – Henry Mar 24 '11 at 23:07
Please make your posts self-contained; the body should have all the information necessary to understand them, not relying on the title for important information. – Arturo Magidin Mar 25 '11 at 3:17

The substitution method works especially well for recursions like $$f(n) = f(n-1) + g(n), \quad f(n) = f(n/2) + g(n),$$ and in any other situation in which $f(n)$ depends on at most one earlier value of $f$. In some cases you can look up the answer. For example, there is the "polynomial method", which is a recipe for solving recurrences of the type $$f(n) = \begin{cases} f(n-1) + P(n) & n > n_0, \\ C & n = n_0. \end{cases}$$ For example, if you define $f(0) = 0$ and $f(n) = f(n-1) + 2n - 1$ then you get using this method that $$f(n) = n^2.$$ A vast generalization is Gosper's algorithm, see also A=B.