So I have the following recurrence relation which I am trying to solve:
T(n) = T(n − 2) + n log n, T(0) = T(1) = 1.
While usually if it is T(n-1) + log n it would just be
T(n) = T(n-i) + log(n-i) + log(n-i-1) + ... log(n), and I can say n-i = 1 ...
But I am having trouble figuring out what to do when T(n-2), and how that affects nlogn.
So we can relate this entire thing to the Hyperfactorial.
The hyperfactorial of a positive integer n is the product of the numbers $1^1,2^2,3^3,4^4,...$
$$H(n) = 1^1 \cdot 2^2 \cdot 3^3 \cdot 4^4 ... n^n$$
now for T(n) we only care about either the even or odd terms of this product (and then taking the logarithm)
since $T(n) = T(n-2) + log(n^n)$
so lets take the hyperfactorial, and square it:
$$H(n)^2 = 1^2 \cdot 2^4 \cdot 3^6 \cdot 4^8 ... n^{2n}$$
now taking this and multiplying each term by a power of two equal to the exponent, means we multiply this entire thing by $2^{n(n+1)}$:
$$2^{n(n+1)} H(n)^2 = 2^2 \cdot 4^4 \cdot 6^6 \cdot 8^8 ... {(2n)}^{2n}$$
but taking the logarithm of that gives us T(n) for even numbers:
$$T(2n) = \log(2^{n(n+1)} H(n)^2)$$
for odd numbers, we actually need all other terms so: $$T(2n+1) + T(2n) = \log(H(2n+1))$$ meaning: $$T(2n+1) = \log(H(2n+1)) - \log(2^{n(n+1)} H(n)^2)$$
now we use the fact that there is an asymptotic formula for the hyperfactorial: $${\displaystyle H(n)=An^{(6n^{2}+6n+1)/12}e^{-n^{2}/4}\left(1+{\frac {1}{720n^{2}}}-{\frac {1433}{7257600n^{4}}}+\cdots \right)\!}$$ where ${\displaystyle A\approx 1.28243}$ is the Glaisher-Kinkelin constant.
This gives us that T(n) for even n is approximately:
$$T_{even}\left(n\right)=\ln\left(n\right)\cdot\frac{\left(n^{2}+2n+\frac{2}{3}\right)}{4}-\frac{n^{2}}{8}+2\ln\left(\frac{A}{\sqrt[12]{2}}\cdot\left(1+\mathcal O\left( \frac{1}{n^2}\right)\right)\right)$$
and if T(n) for odd n is approximately:
$$T_{odd}\left(n\right)=\ln\left(n\right)\cdot\frac{\left(n^{2}+2n+\frac{2}{3}\right)}{4}-\frac{n^{2}}{8}+\frac{1}{4}-\ln\left(\frac{A}{\sqrt[6]{2}}\cdot\left(1+\mathcal O\left(\frac{1}{n^{2}}\right)\right)\right)$$