-1

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.

lobsterj
  • 9
  • $$T(n) \approx \frac{1}{4} n^2 log_2(n) - \frac{n^2}{ln(256)} + \frac{1}{2} n log_2(n) + \mathcal O (log_2(n))$$

    the idea is to use integrals instead of infinite sums and then play around with the function a bit

     – Control May 10 '23 at 01:11
  • 1
    "Solve" separately the two subsequences $(T(2k))$ and $(T(2k+1))$, with your "usual" procedure. – Anne Bauval May 10 '23 at 02:17
  • You can also simplify the problem by considering the sequence $a_n := T(n) - T(n-1)$ instead. – Abezhiko May 13 '23 at 11:15

1 Answers1

1

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)$$

Control
  • 162