How do you find the closed form of these recurrence relations? I found these two recurrence relations in an old textbook and was hoping someone could show me how to solve them for their closed form.  If not, a final answer would also be appreciated, as it helps me reason out the iterative process (I've tried using online calculators to give me an answer but I haven't had the best of luck).
$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, T(0) = 0$ and e,f,g > 0 and n is a multiple of f
 A: The second relation reads $T(kf)=eT((k-1)f)+g$ for all $k\geq 0$.
Write $T(kf)=x_kg$.
Then $x_0=0$ and $x_k=ex_{k-1}+1$.
Case 1: $e=1$ then $x_k=k$ (induction) and so 
$$T(kf)=kg.$$
Case 2: $e\neq 1$ then $\frac{1}{1-e}$ is a constant solution and the general solution of the homogeneous relation$x_k=ex_{k-1}$ is the geometric sequence $\lambda e^k$. So $x_k=\frac{1}{1-e}+\lambda e^k$.
For $k=0$, we find $0=\frac{1}{1-e}+\lambda $, so $x_k=\frac{1-e^k}{1-e}$.
Hence
$$
T(kf)=\frac{(1-e^k)g}{1-e}.
$$
Your first relation tells you actually that $T(2^k)=T(2^{k-1})+k$.
Setting $y_k=T(2^k)$, we have to solve $y_k=y_{k-1}+k$ with $y_0=1$.
So $y_k=1+1+2+\ldots+k=1+\frac{k(k+1)}{2}$ (induction).
So we have
$$
T(2^k)=1+\frac{k(k+1)}{2}=\frac{k^2+k+2}{2}.
$$
Edit: There is a general technique to solve linear recurrence relations of order $n\geq 1$ of the type
$$
x_{k}=c_{1}x_{k-1}+\ldots+c_{n-1}x_{k-n+1}+c_nx_{k-n}+C\quad\forall k\geq n.
$$
This should be seen, somehow, as a discrete linear ODE of order $n$.
The key object to consider is the characteristic polynomial of the homogeneous equation:
$$
x^n-c_{n-1}x^{n-1}-\ldots-c_1x-c_0.
$$
Strategy:
1) Find a particular solution. This depends very much on $C$. This could actually depend on $k$, in the most general situation. Here $C\neq 0$ is constant, and there are several cases to consider:


*

*If $P(1)\neq 0$ (case 2 above), then look for a particular solution which is constant. You will find that $x_k=\frac{C}{P(1)}$ works.

*If $P(1)=0$ and $P'(1)\neq 0$ (case 1 above), then look for a particular solution of the form $x_k=Ak$. You'll find $A$.

*If $P(1)=P'(1)=0$ and $P''(0)\neq 0$, look for a particular solution of the form $x_k=Ak^2$.

*And so on...
2)Solve the homogeneous equation:
$$
y_{k}=c_{1}y_{k-1}+\ldots+c_{n-1}y_{k-n+1}+c_ny_{k-n}\quad\forall k\geq n.
$$
Theory tells you that this is an $n$-dimensional subspace of the vector space of all complex sequences.
In the case where the roots of the characteristic polynomial are pairwise distinct $r_1,\ldots,r_n$, the general homogeneous solution can be written:
$$
y_k=A_1r_1^k+\ldots +A_nr_n^k.
$$
If there are repeated roots, say $r_j$ with multiplicity $3$, then the correpond ing term is of the form $(A_jn^2+B_jn+C_j)r_j^k$.
3) The general solution of your initial relation is the sum of the particular solution found in 1) and of the general homogeneous solution found in 2).
If there are initial conditions ($x_0$, $x_1$ given...), this will lead to restricitions on the constants $A_j$, or even to a full determination of them.
Note: Here, it is actually pretty simple since it is of order $1$.
For $x_k=ex_{k-1}+1$, the characteristic polynomial is
$$
P(x)=x-e.
$$
- Case 1: $e=1$ and then $P(1)=0$ and $P'(1)\neq 0$ so we look for a particular solution of the form $x_k=Ak.$ We find that $A=1$ and $x_k=k$ works.
The homogeneous equation clearly leads to a general constant homogeneous solution $y_k=B$. Now your general solution is $x_k=k+B$. The initial condition $x_0=0$ yields $B=0$ so $x_k=k$.
(Note that like I said initially, it is easy to see and prove by induction that $x_k=x_{k-1}+1$ with $x_0=0$ leads to $x_k=k$).


*

*Case 2: $e\neq 1$ so that $P(1)\neq 0$. Then a particular solution is the constant sequence $x_k=1/P(e)=1/(1-e)$ and the general homogeneous solution is $y_k=Ae^k$. SO the general solution is $x_k=Ae^k+1/(1-e)$. And we find $A$ by the initial condition $x_0=0$.

A: For example the firt one:
$$T(1)=1\;\;,\;\;T(2)=T(1)+\log_22=1+1=2\;\;,\;\;T(4)=T(2)+\log_24=2+2=4$$
$$T(8)=T(4)+\log_28=4+3=7\;\;,\;\;T(16)=T(8)+\log_216=7+4=11$$
So the sequence seems to be $\,1,2,4,7,11,16,22,\,\ldots,a_{n-1}+n-1\,\ldots\,$
