text: Q:
  
  What is the bound of $T(n) = T(n-2) +n\log(n)$?
  
  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.
  
  A:
  
  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.
  
  