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

Question

I was trying to solve

$T(n) = T(n-1)+\log^2(n)$

using substitution method and variables substitution but I can't find the correct answer.

My attempt:

Let $m = \log(n)$

then $T(2^m) = T(2^m-1)+m^2$

next, we assume that $S(m) = T(2^m)$

so $S(m) = S(m-1)+m^2$ but here I'm stuck with this passage and I can't continue. Am i doing something wrong? Any tips?

Answer 1

$T(n)-T(n-1)=\log^2(n)$, then $(T(n)-T(n-1))+(T(n-1)-T(n-2))+\ldots+(T(2)-T(1))=\log^2(n)+\ldots+\log^2(2)$, so $T(n)-T(1)=\log^2(n)+\ldots+\log^2(2)$, $$T(n)=T(1)+\sum_{k=2}^n\log^2(k)$$.

Answer 2

Rearranging gives $$T(n)-T(n-1)=\log^2(n)$$ which is then convenient for telescoping, i.e. $$\begin{align} &T(n)&-T(n-1)&=\log^2(n)\\ &T(n-1)&-T(n-2)&=\log^2(n-1)\\ &T(n-2)&-T(n-3)&=\log^2(n-2)\\ &\cdots \\ &T(3)&-T(2)&=\log^2(3)\\ &T(2)&-T(1)&=\log^2(2)\\ \end{align}$$

Summing gives

$$T(n)-T(1)=\sum_{r=2}^{n}\log^2 r\\ T(n)=T(1)+\sum_{r=2}^{n}\log^2 r$$