# Solving for the closed form of a recurrence relation

Can someone concisely explain how we can find the closed form of a recurrence relation? I know the iterative process is generally the preferred method, but I'm having trouble deriving the steps and coming to a final solution. Here are two questions I've obtained from an old textbook. If possible, I'd greatly appreciate if the "where n is a power of 2" and "where e,f,g are positive integers and n is a multiple of f" effect the decisions we make whilst trying to conclude with a closed form.

$T(n) = T(\frac{n}{2}) + \log_2{n}, T(1) = 1$ and n is a power of 2

$T(n) = eT(n-f)+g$ and e,f,g > 0 and n is a multiple of f

Thank you!

-

For the first $T(n)$ is not defined unless $n$ is a power of $2.$ We are given $T(1)$ and can use the recurrence to find $T(2),$ but there is no way to find $T(3)$ unless we view the division as integer division and say $3/2=1.$ For recurrences like this, we usually care about asymptotic behavior, so we can just think about powers of $2.$

Similarly in the second, having $n$ a multiple of $f$ means the recurrence will bottom out at $0.$ Having $e,f,g \gt 0$ makes sure $T(n)$ doesn't go negative. The text is being careful to give well-stated problems.

Added: for the first, define $n=2^k$, so $k=\log_2 n$ and define $S(k)=T(2^k)=T(n)$. $S(k)$ is defined for all $k$. The recurrence becomes $S(k)=S(k-1)+k, S(0)=1$ By inspection we can see that $S(k)=1+\sum_{i=1}^k i=1+\frac 12 k(k+1)$ so $T(n)=1+\frac 12 \log_2 n (\log_2 n +1)$

For the second, let $m=\frac nf$ and define $P(m)=T(fm)=T(n)$. You didn't give a base case, so I will assume $T(0)=P(0)=0$. The recurrence becomes $P(m)=eP(m-1)+g$. If we just write out $P(3)=eP(2)+g=e(P(1)+g)+g=e(e(P(0)+g)+g)+g=e^2g+eg+g$ we can see that $P(m)=g\frac {e^m-1}{e-1}$ by summing the geometric series. You can make it more formal, but that is the answer. Now you would need to translate that back to the original $T(n)$

-
Thank you! Do you have any idea of a solution for these recurrences, or possible something online that can compute them for me (if the closed form by hand isn't readily accessible)? –  Bob John Feb 6 '13 at 1:15
For the first let $k=\log_2 n$, for the second $m=n/f$ Both become fairly simple. –  Ross Millikan Feb 6 '13 at 1:20
I'm sorry, I don't know how to proceed. Do you mind elaborating? I'm trying to use wolfram, but apparently I can't specify unknown values such as e,f, and g –  Bob John Feb 6 '13 at 1:23
@BobJohn: See the added info. –  Ross Millikan Feb 6 '13 at 14:49