Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)
I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach.


You are correct. While the master theorem can yield asymptotically tight bounds, the question asks you to prove an exact inequality, $T(n) \leq 8n^2$ for all for $n\in\mathbb{N}_0$.

Since this is a proposition on natural numbers, we should use mathematical induction. Because $T(n)$ is related to $T(\lfloor n/2\rfloor)$, we will use strong induction. 


Base case. $n=0$:   $T(0)=0\le 8\cdot0^2$.

Inductive step. Assume for all $k &lt; n$, prove for $n &gt;0$:

$$T(n)=3T(\lfloor{n/2}\rfloor) + 2n^2\le3\cdot8(\lfloor{n/2}\rfloor)^2 + 2n^2\le24(n/2)^2+2n^2=8n^2$$

Note that since $\lfloor{n/2}\rfloor\lt n$, we can apply the induction hypothesis to obtain $T(\lfloor{n/2}\rfloor)) \leq 8(\lfloor{n/2}\rfloor)^2$.

Exercise 1. Show that $T(n) \lt 8n^2$ for all $n &gt;0$.

Exercise 2. What is the largest $n$ such that $T(n) \le 7n^2$?



Exercise 3. Show that $\dfrac{T(n)}{n^2}\to8$ when $n\to\infty$.