Tight Upper Bound for $\sum_{i=1}^ni \log i$

873 Views Asked by At

Can we find the tight upper bound for $\sum_{i=1}^ni\log i$

My approach: $$\sum_{i=1}^ni\log i\leq\sum_{i=1}^n\log {i^i}=\log\left(\prod_{i=1}^ni^i\right)\leq \log n^{n^2}= n^2\log n$$

My upper bound for the summation is $n^2\log n.$

1

There are 1 best solutions below

0
On BEST ANSWER

$$\lfloor x\rfloor \log\lfloor x\rfloor<x\log x$$

Integrating from $1$ to $n+1$,

$$\sum_{i=1}^n i\log i<\int_1^{n+1}x\log x\,dx=\frac14 ((1 + n)^2 (2 \log(1 + n)-1)+1).$$

Better accuracy with the Euler-Maclaurin summation formula, but

$$\frac{n^2\log n}2$$ is the main term.