How to find a lower bound for $T(n)=T(n-1)+n^2+n^2\log n$?
This question is in continuation to the following one : Find an upper bound for $T(n)=T(n-1)+n^2+n^2\log n$
For upper bound the logic is to "round" the indices towards $n$, but I really don't have a clue how to go about the lower bounds.
On
Obviously, $$T(n)=T(0)+\sum^n_{k=1}(k^2+k^2\log k).$$ Now we know that $$\sum^n_{k=1}k^2=\frac{n(n+1)(2n+1)}{6}=f(n).$$ Then, by partial summation, $$\sum^n_{k=1}k^2\log k=\sum^n_{k=1}[f(k)-f(k-1)]\log k=f(n)\log(n+1)-\sum^n_{k=1}f(k)\log\left(1+\frac1{k}\right),$$ and since $\log\left(1+\frac1{k}\right)<\frac1{k},$ $$\sum^n_{k=1}k^2\log k\ge f(n)\log(n+1)-\sum^n_{k=1}\frac{f(k)}{k}=f(n)\log(n+1)-\frac1{6}\left(2f(n)+3\frac{n(n+1)}{2}+n\right)$$ I think the rest should be clear.
From the previous question I restate the summation and I assume that you are looking for an asymptotic lowerbound $T(n) = \Omega(f(n))$ and since in the previous question you already obtained $T(n) = O(n^3 \log n)$ we will aim for the same lowerbound.
$$ T(n) = \overbrace{\sum_{i=1}^n i^2}^{\Omega(n^3)} + \sum_{i=1}^n i^2 \log(i) \overset{(*)}{\geq} \Omega(n^3) + \frac{n}{2}\left((\frac{n}{2})^2\log(n/2) \right) = \Omega(n^3\log(n)) $$ $(*)$ The trick is to retain only half of the term in the sum and lowerbound them by the central term. For example, assuming $f(n)$ is positive and increasing, then $f(1) + f(2) + f(3) + f(4) \geq f(3) + f(3)$ (we throw away $f(1)$ and $f(2)$ which creates a lowerbound on the sum and we then lowerbound the remaining term ($f(3)$ and $f(4)$) by the smallest remaining term which is $f(3)$. More generally $\sum_i^n f(i) \geq \frac{n}{2} f(n/2)$.