Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 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 master method applies only in some situations (see the link); when it does apply, it tells you what you'll get if you use the recursion tree method.

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.