How to solve $ T(n) = 2T(n-2) + n\log n$?

Question

I came across this recurrence relation while preparing for my math test:

$T(n) = 2T(n-2) + n\log(n)$

I wasn't able to solve it and would appreciate your help.

Answer 1

This is a linear difference equation. It can be solved as

$T_n = T_n^h + T_n^p$ where

$$ T_n^h-2T_{n-2}^h = 0\\ T_n^p-2T_{n-2}^p = n \ln n $$

The homogeneous solution gives

$$ T_n^h = C_1 2^{\frac{n}{2}}+C_2(-1)^n2^{\frac{n}{2}} $$

now making $T_n^p = C_1(n) 2^{\frac{n}{2}}+C_2(n)(-1)^n2^{\frac{n}{2}}$ using the parameter variation technique due to Lagrange and assuming $C_2(n) = 0$ we obtain for $C_1(n)$

$C_1(n)-C_1(n-2) = \frac{n\log n}{2^{\frac{n}{2}}}$

The final solution is quite involved (formally) and can be obtained with the contribution of a suitable symbolic processor.