Recursion Tree, Solving Recurrence Equations

Question

As far as I know There are 4 ways to solve recurrence equations : 1- Recursion trees 2- Substitution 3 - Iteration 4 - Derivative

We are asked to use Substitution, which we will need to guess a formula for output. I read from CLRS book that there is no magic to do this, i was curious if there are any heuristics to do this?

I can certainly have an idea by drawing a recurrence tree or using iteration but, because the output will be in Big-OH or Theta format, formulas doesnt necessarily match.

Does any one have any recommendation for solving recurrence equations using substitution?

Answer 1

Please note that the list of possible ways to solve recurrence equations is definitely not complete, its merely a set of tools they teach Computer Scientists, because they will most likely solve most of your problems.

For exact solutions of recurrence equations mathematicians use a tool called generating functions. Generating functions give you exact solutions, and in general are more powerful than the master theorem.

There is a great resource online to learn about the here. http://www.math.upenn.edu/~wilf/DownldGF.html

If you go through the first couple examples you should get the hang of it in no time.

You need some math background and understand rudimentary taylor series. http://en.wikipedia.org/wiki/Taylor%5Fseries

Generating functions are also extremely useful in probability.