Show that $T(n) = 2T(\lfloor n/2\rfloor) + n$ is $\Omega(n\log n)$ using substitution
One way to go around the difficulties is as follows.

First, you prove that $T(n) = \Omega(n \log n)$ when $n = 2^k$.

Second, you prove that $T(n)$ is monotone (given monotone base cases).

Third, you finish the proof as follows. Let $m \leq n &lt; 2m$, where $m = 2^k$. Then
$$
 T(n) \geq T(m) = \Omega(m \log m) = \Omega(n \log n).
$$
Details left to you.