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!
 A: 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)$
