How to solve the recurrence relation for tight asymptotic bound without using master theorem? I have the following recurrence in my problem: $$T(n)= 4T(n/2)+n.$$
I have solved it by substitution by assuming the upper bound $O(n^3)$ but in solving it for $O(n^2)$ i am having some problems.I know that this problem is more tightly bounded to $O(n^2)$. Following are the attempts made by me through induction:
Assume
$$T(k)\leqslant ck^2, \mbox{ for } k.$$
Now we have
$$T(n)=4T(n/2)+n,$$
$$T(n)=4c(n^2/4)+n, \mbox{ from induction hypothesis as } n/2<n,$$
$$\ldots$$
$$T(n)=cn^2+n.$$
So in the end if i have to prove this tight bound the requirement becomes    
$$cn^2 + n \leqslant cn^2.$$
Now i don't understand how to get out of this with induction not using the master theorem? I am a beginner in this so please forgive me if i have produced any syntatical errors. Thanks in advance.
 A: 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.
A: If $n=2^k$, then the recurrence 
$$T(n)=4T(n/2)+n,$$
becomes
$$
T\big(2^{k}\big)=4T\big(2^{k-1}\big)+2^k,
$$
and hence, if we set $S(k)=T\big(2^k\big)$, then $S(k)$ satisfies the recurrence relation
$$
S(k)=4S(k-1)+2^k,
$$
and therefore
$$
\frac{S(k)}{4^k}=\frac{S(k-1)}{4^{k-1}}+2^{-k}.
$$
Thus
$$
\frac{S(k)}{4^k}=2^{-k}+2^{-k+1}+\cdots+2^{-1}+S(0)=S(0)+1-\frac{1}{2^k},
$$
and consequently
$$
S(k)=4^k\big(S(0)+1\big)-2^k,
$$
and finally, replacing back $n=2^k$ and $S(k)=T(n)$, we obtain
$$
T(n)=n^2\big(T(1)+1\big)-n.
$$
