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