I am given the following recurrence relationship: \begin{align} T(n) &= T(n-2) + n\log(n), \\ T(1) &= T(0) = \mathrm{constant}. \end{align}
I need to find the order for the recurrence.
So, using the iterative methodology, what I have until now is as follows:
\begin{align} T(n) ={}& T(n-2) +n\log(n) \\ ={}& T(n-4) +(n-2)\log(n-2) +n\log(n) \\ & \vdots \\ ={}& T(n-2k) +\sum_{i=0}^{n/2} (n-2i)\log(n-2i) \tag{where $2k=n$} \\ ={}& T(0) +\sum_{i=0}^{n/2} (2i)\log(2i) \tag{reversed order} \end{align}
I am unsure as to how to progress from here on with the summation. I believe it should be along the lines of $(n^2)\log(n)$ but cannot seem to conclusively prove it. The reason I say this is because for large $n$, the quantity $(n-2i)\log(n-2i)$ can be roughly estimated to $n\log n$, can it not?
Any help/guidance will be appreciated.
You can follow a sloppy estimate and switch to integration: $$\sum_{i=0}^{n/2} (2i)\log(2i) \approx \int_0^{n/2} 2x\log x\,\mathrm dx,$$ which will yield $n^2 \log n/4 - n^2/16 = O(n^2 \log n)$. So your solution is right.