We claim that if:
$$
T(n) = 2T(n/2) + n
$$
then $T(n) = \Theta(n \log n)$. To see this, it suffices to prove by induction on $n$ that there exist constants $c,d,n_0 \geq 1$ such that for all $n \geq n_0$, we have that:
$$
cn \log n \leq T(n) \leq dn\log n \tag{$\star$}
$$
Base Case: I'll let you do this part.
Induction Hypothesis: Assume that $(\star)$ holds for all $n' < n$.
It remains to prove that $(\star)$ holds for $n' = n$. Indeed, observe that:
\begin{align*}
2T(n/2) + n &= T(n) = 2T(n/2) + n \\
2(c \tfrac{n}{2}\log \tfrac{n}{2}) + n &\leq T(n) \leq 2(d\tfrac{n}{2} \log \tfrac{n}{2}) + n &\text{by the ind. hyp.} \\
cn(\log n - \log 2) + n &\leq T(n) \leq dn (\log n - \log 2) + n \\
(cn\log n) + (\underbrace{1 - c \log 2}_{\geq~0})n &\leq T(n) \leq (dn \log n) - (\underbrace{d\log 2 - 1}_{\geq~0})n \\
cn \log n &\leq T(n) \leq dn\log n
\end{align*}
where the last step used the fact that we can choose $c \leq \frac{1}{\log 2}$ and $d \geq \frac{1}{\log 2}$.
The so-called master theorem is not needed anyway, neither here nor in many other questions of the same ilk asked on math.se so the fact that you require a solution not using it is quite welcome... Here we go:
Just as when studying ordinary differential equations, we start with the linear part of the relation, that is, $$T(n)=4T(n/2)=\color{blue}{2}^{\color{red}{2}}T(n/\color{blue}{2}),$$ or equivalently, $$\frac{T(n)}{n^{\color{red}{2}}}=\frac{T(n/2)}{(n/2)^{\color{red}{2}}},$$ which is obviously solved by $$T(n)=Cn^{\color{red}{2}},$$ for some constant $C$. This suggests to transform the relation at hand, using $$S(n)=T(n)/n^2.$$ One gets $$S(n)=S(n/2)+1/n.$$ Better, but not quite the best possible formulation... Iterating the identity involving $S$ yields the values of $S$ at $n/2$, $n/4$, and so on, hence we could as well consider from the start $$R(k)=S(2^k)=T(2^k)/4^k.$$ Now the relation at hand becomes $$R(k)=R(k-1)+1/2^k,$$ that is, $$R(k)=R(0)+1/2+1/4+\cdots+1/2^k=R(0)+1-1/2^k,$$ or equivalently, $$T(2^k)=4^k(T(1)+1)-2^k,$$ which proves that $$T(2^k)=\Theta(4^k),$$ for every nonnegative $T(1)$.
And now comes one most unsatisfying practice of the field, which is to pretend that this last identity implies that $$T(n)=\Theta(n^2),$$ although it does not (and anyway, what would be the identity we started from when $n=3$?).
In retrospect, the exact formula we found suggests that the upper bound $$T(n)\leqslant Cn^2-n,$$ should carry through easily. And behold! if this upper bound holds for $n/2$, then $$T(n)=4T(n/2)+n\leqslant4(C(n/2)^2-(n/2))+n=Cn^2-n,$$ as desired. Likewise, every lower bound $$T(n)\geqslant cn^2-n,$$ is hereditary.
Best Answer
You're likely to get a comment about asking multiple questions as one big one, but to get you started, I'll do an iterative expansion.
Let $n=2^k$, since strictly speaking those are the only values for which your recurrence makes sense. Then your recurrence takes the form $$ T(2^k) = 2^2T(2^{k-1})+2^{2k}k $$ Now let's iterate $$\begin{align} T(2^k) &= 2^2[T(2^{k-1})]+2^{2k}k \\ &= 2^2[2^2T(2^{k-2})+2^{2(k-1)}(k-1)]+2^{2k}k\\ &\qquad= 2^4T(2^{k-2})+2^{2k}(k-1)+2^{2k}k\\ &= 2^4[2^2T(2^{k-3})+2^{2(k-2)}(k-2)]+2^{2k}(k-1)+2^{2k}k\\ &\qquad= 2^6T(2^{k-3})+2^{2k}(k-2)+2^{2k}(k-1)+2^{2k}k \end{align}$$ and the general pattern appears to be $$\begin{align} T(2^k) &= 2^{2j}T(2^{k-j})+2^{2k}(k-j+1)+2^{2k}(k-k+2)+\cdots+2^{2k}k\\ &= 2^{2j}T(2^{k-j})+2^{2k}((k-j+1)+(k-j+2)+\cdots k) \end{align}$$ assuming we've correctly guessed the pattern, we let $j=k$ and obtain $$ T(2^k)= 2^{2k}T(2^0)+2^{2k}(1+2+3+\cdots k)=(2^k)^2+(2^k)^2\frac{k(k+1)}{2} $$ Finally, recall that we set $n=2^k$ so $k=\lg n$ so we have the solution $$ T(n) =n^2+n^2\frac{\lg n(\lg n+1)}{2}=\Theta(n^2\lg^2n) $$ Now all you have to do is complete the remaining two parts. (grins)