Prove correctess of recurrence result by mathematical induction
We prove by induction that for every $n\in\mathbb{N}$ it holds that $T(n)=2n^2-n$.
The inductive hypothesis is that for all $1\le k&lt;n$ we have:

$T(k)=2k^2-k$.

We proceed to show that $T(n)=2n^2-n$.

By definition, $T(n)=4T\left(\frac{n}{2}\right)+n$. Since $\frac{n}{2}&lt;n$, we can use our inductive hypothesis and obtain $T\left(\frac{n}{2}\right)=2\left(\frac{n}{2}\right)^2-\frac{n}{2}$. After substituting this back into $T(n)$ we have:

$T(n)=4\left(\frac{n^2}{2}-\frac{n}{2}\right)+n=2n^2-n$.