As title, for this recursive function $T(n) = T(n-2) + \log_2 n$, I worked out how to prove that it belongs to $O(n\log n)$; however I'm having trouble proving it to be also $\Omega(n\log n)$, i.e. lower-bounded by $n\log_2 n$ asymptotically.
Following the standard inductive procedure provided by CLRS algorithm text, I have: Assuming for some integer n such that for all $m<n$, $T(m) \geqq Cm\log_2m$, then:
$$T(n) \geqq C(n-2)\log_2(n-2) + \log_2 n$$
From this point on, it gets tricky (for me at least) to deduce the conclusion that $T(n) \geqq Cn\log_2n$
One possible way to move on is to give an observation that for all $n\geqq 4$, $\log_2(n-2)\geqq \log_2(n/2)=\log_2 n - 1$, but then this will generate a $-Cn$ term that I cannot get rid of.
The solutions manual of CLRS 2e suggests strengthening the induction hypothesis, i.e. assuming for all $m<n$, $T(m) \geqq Cm\log_2 m + Dm$ instead. It then arrives at $T(n) \geqq Cn\log_2 n$ and claims the proof is complete, which I think is incorrect as an inductive proof must arrive at exactly the same expression as the inductive hypothesis ($T(n) \geqq Cn\log_2 n + Dn$). In fact, I don't see how introducing a $Dm$ term here makes it easier at all to arrive at $T(n) \geqq Cn\log_2n + Dn$. I think I'm stuck. Any insight is much appreciated!