Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
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
1  
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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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