Solving the Recurrence Relation $T(n)=T(n-1)+n\log n$

Question

Solve $\;T(n)=T(n-1)+n\log n$

This is how I started:

$$\begin{align} T(n)&=T(n-2)+(n-1)\log(n-1)+n\log(n)\\ &=T(n-3)+(n-2)\log(n-2) + (n-1)\log(n-1)+n\log(n) = \end{align}$$

Actually, I'm stuck here. I can't find a way to reformat the log..

Answer 1

You should begin to notice a pattern after some iterations:

$$\begin{align} T(n) &= T(n-1) + n \log(n)\\ &= T(n-2) + (n-1) \log (n-1) + n \log (n)\\ &= T(n-3) + (n-2) \log(n-2) + (n-1) \log (n-1) + n \log (n)\\ &= ...\\ &= T(0) + \sum_{k=1}^n (n-k) \log(n - k)\\ &= T(0) + \sum_{k=1}^n k \log( k) \end{align}$$

We recall two properties of logarithms:

$$\log(x^y) = y \log(x) \;\;\;\;\; \log(xy) = \log(x) + \log(y)$$

Thus,

$$\sum_{k=1}^n k \log(k) = \log\left( \prod_{k=1}^n k^k \right)$$

This iterated product in the center is known as the hyperfactorial function. It may sometimes be denoted by

$$H(n) = \prod_{k=1}^n k^k$$

It grows insanely fast, with $H(14)$ being on the order of a googol ($10^{100}$). It does have its asymptotic growth rate known

$$H(n) \sim An^{(6n^2+6n+1)/12}e^{-n^2/4}$$

where $A$ is the Glaisher-Kinkelin constant ($A \approx 1.282$). That said, I can't really find any closed forms for it, so we might be stuck here. From a post by Ragib Zaman on MSE, we do have something close for the logarithm of the hyperfactorial:

$$\log H(n) = \frac{1}{2}n^2 \log n - \frac{n^2}{4} + \mathcal{O}\left( n\log n \right).$$

where, I assume, $O(\cdot )$ here is the big-$O$ notation.

---

I'm afraid that's all I can really dig up on the matter. At least anything that looks useful.

For what it's worth we're actually going over nonhomogenous recurrence relations in my combinatorics class and I did try to solve it (as opposed to your "just repeatedly iterate the recurrence" method) via some of the methods we have been taught there, but nothing really came of it. Unsurprisingly, since it's relatively introductory stuff. Oh well.

My guess is that the closest you'll get to a closed form is referencing the hyperfactorial, unless some brilliant answer comes along.

Answer 2

Added for your curiosity.

Eevee Trainer provided a very good and detailed answer.

There is a closed form expression for $T_n$; assuming $T_0=k$, it write $$T_n=k+\zeta ^{(1,0)}(-1,n+1)-\zeta ^{(1,0)}(-1,1)$$ where appears the partial derivative of the generalized Riemann zeta function.

Using asymptotics, $$T_n=k+\log (A)+\frac{6n^2+6n+1}{12} \log (n)-\frac{n^2}{4}+\frac{1}{720 n^2}+O\left(\frac{1}{n^4}\right)$$ Eevee Trainer already gave

To give you a taste of the accuracy, using $k=1$ and $n=10$, the exact solution would be $$1+50 \log (2)+27 \log (3)+15 \log (5)+7 \log (7)\approx 103.082830552$$ while the above expansion leads to $$\log (A)+\frac{661 }{12}\log (10)-\frac{1727999}{72000}\approx 103.082830572$$