Find an upper bound for $T(n)=T(n-1)+n^2+n^2\log n$

Question

Find an upper bound for $T(n)=T(n-1)+n^2+n^2\log n$.

Not sure but it looks like the series is: $$ 1^2+2^2+3^2+...+n^2+\log 1+2^2\log 2+3^2\log 3+...+n^2\log n=\\ =\sum_{i=0}^n i^2+\sum_{i=0}^n i^2\cdot\log i\le n^3+n^3 \log n $$ Is it correct?

Answer 1

Your upper bound proof looks fine to me. Assuming $T(0) = 0$, and defining $t(n) = n^2 + n^2 \log n$, I would express your proof as follows. Because $t(n)$ increases with $n$ for positive integers $n$, $$T(n) = \sum_{i=1}^n t(i) \le n t(n) = n^3 + n^3 \log n.$$

If you want a tighter upper bound, and you're willing to do a little calculus, you can make the following argument. Because $t(x)$ increases with $x$ for real $x \ge 1$, $$T(n) = \sum_{i=1}^n t(i) \le \sum_{i=1}^n \int_i^{i+1} t(x)\,dx = \int_1^{n+1} t(x)\,dx.$$ The integral of $t(x)$ is $$\tau(x) = \int t(x)\,dx = \frac{x^3}{9}\left(2 + 3 \log x \right)+C.$$ Therefore $$T(n) \le \tau(n+1) - \tau(1) < \frac{(n+1)^3}{9}\left(2+3 \log (n+1) \right).$$