I just had an exam in my algorithms class and this was a question on it. I was able to craft a solution, but I'm not sure if my proof has errors.
$$\begin{align} &\frac{n}{2}-3 < n & \forall n > 0 \tag 1\\ &\lg\left(\frac{n}{2}-3\right) < \lg(n) & \forall n > 0\tag 2\\ &\lg(n) < n & \forall n > 0\tag 3 \end{align}$$
Proceed inductively. Base case usually holds for recursive algorithms as $T(1)$ is $O(1)$ or some constant time.
Assume $T(k) = O(k\lg k)$ for all $k < n$, that is $T(k) \leq ck\lg k$. Then, \begin{align} T(n) &= 2T(\frac{n}{2} -3) + n\\ &\leq \left(2c\cdot(\frac{n}{2} -3)\cdot \lg\left(\frac{n}{2} -3\right)\right) + n\\ &= (cn-6c)\cdot \lg(n) + n \quad \text{by (2)}\\ &= cn\lg{n}-6c\lg n + n \\ &\leq cn\lg{n} + n + cn \\ &= cn\lg{n} - (-1-c)n \\ &\leq cn\lg{n} \quad\text{for all $c>1$} \end{align}
Thus, it follows by definition that $T(n) = O(n\lg{n})$
Did I make too many assumptions about the behavior of the inequalities?
Thanks in advance!
Assume that $T(k)\leqslant ck\log(k)$ for every $k\lt n$, for some $n\geqslant30$ and some $c\geqslant2$. Then $T(n)\leqslant c(n-6)\log(n-6)-c(n-6)\log2+n$. In particular, $T(n)\leqslant cn\log(n)-R(n)$ with $R(n)=2(n-6)\log2-n\geqslant.3n-9$ hence $R(n)\geqslant0$ and $T(n)\leqslant cn\log(n)$.
Thus, choosing $c\geqslant\max\{2\}\cup\{T(n)/(n\log n);n\leqslant30\}$ one gets a property $T(n)\leqslant cn\log(n)$ which is hereditary for $n\geqslant30$ and true for $n\leqslant30$. QED.