I need to find an approximation for the recurrence relation: $$f(n)=f(n-1)+n\log n \qquad n \in \mathbb{N}$$ (to be more precise I need to find an upper bound).
I tried dividing the LHS and RHS by $n!$ for $n \ge 2$ ($n=1$ is the base case where $f(1) = 0$): $$ {f(n) \over n!}={f(n-1) \over n!}+{n\log n \over n!} = {\log n \over (n-1)!}+{\log n \over (n-2)!}+...+{\log n \over 1!} = \sum_{i=2}^n {\log n \over (n-i)!}= $$ $$ = \log n\sum_{i=2}^n {1 \over (n-i)!} $$
At the point the expression $\sum_{i=2}^n {1 \over (n-i)!} $ reminds of the series of $\sum_{i=0}^{\infty} {x^i \over i!} =e^x$ where in our case $x=1$. I'm wondering if we can arrive to the conclusion that: $$ {f(n) \over n!} \le \log(n) \cdot e \qquad \Rightarrow f(n) \le \frac{\log(n) \cdot e}{n!} $$
Hint We may rewrite $f$ more explicitly as $$f(n) = \sum_{k = 1}^n k \log k .$$ Then, since the function $x \mapsto x \log x$ is increasing, we may bound $f$ above by $$\int_a^{b(n)} x \log x \,dx$$ for suitable $a, b(n)$.