Incorrect inequality after verifying a recurrence solved using the master method I am trying to solve the recurrence  

$$T(n) = 4 T \Big( \frac{n}{2} \Big) + n .$$

using the master method and got $\Theta(n^2)$ using the first case theorem: 

If $f(n) = O(n^{\log_{b}a-\epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta \left(n^{\log_b a} \right)$.

However when I verify the upper bound using the substitution method it seems I arrive at a contradiction:
After assuming that $T \left( \frac{n}{2} \right) \leq c(\frac{n}{2})^{2}$ and then substituting I get 
$$
\begin{align*}
T(n) &= 4c \left( \frac{n}{2} \right)^2 + n

\\ T(n) &= 4c \cdot \frac{n^2}{4}  + n 

\\ T(n) &= cn^{2}+ n  \leq  cn^2 ,
\end{align*}
$$ which is obviously a contradiction. 
Obviously there is something I am not seeing here or overlooked. Would like to have it pointed out.  
 A: You are assuming $T(\frac{n}{2})=c(\frac{n}{2})^2$ and trying to prove $T(n) \le cn^2$.
Instead, you can only obtain that $T(n)=4T(\frac{n}{2})+n \le cn^2+n$, which does not contradict anything.
Hint. To actually prove this, you might want to try a different inductive hypothesis, perhaps a quadratic polynomial in $n$.
A: If $H_k$ is the hypothesis that $T(2^k)=c4^k-2^k$, then, for every $k\geqslant0$, $H_k$ implies $H_{k+1}$. Since $H_0$ holds for $c_T=T(1)+1$, this proves that, for every $k\geqslant0$,
$$
T(2^k)=c_T4^k-2^k.
$$
To deal with indices which are not powers of $2$, one must assume the following:

The sequence $(T(n))_n$ is nondecreasing.

Then, for every $n\geqslant1$, there exists $k$ such that $2^k\leqslant n\lt2^{k+1}$, hence
$$
T(n)\leqslant T(2^{k+1})= c_T4^{k+1}-2^{k+1}\leqslant4c_T4^{k}\leqslant4c_Tn^2.
$$
Likewise, $4^k\gt\frac14n^2$ and $2^k\leqslant n$ hence
$$
T(n)\geqslant T(2^k)=c_T4^k-2^k\geqslant\tfrac14c_Tn^2-n.
$$
Finally,  for every $n\geqslant1$, 
$$
\tfrac14c_T^2n^2-n\leqslant T(n)\leqslant4c_Tn^2,
$$
and $n=o(n^2)$, hence $T(n)=\Theta(n^2)$.
