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

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?

• what's $S(m)$ in terms of $S(m-2)?$ then continue to $S(1).$ – Ehsan M. Kermani Aug 18 '14 at 17:02
• @EhsanM.Kermani Can I consider $S(m) = S(m-i)$ where $i$ goes from $1$ to $m$? – Gabriele Salvatori Aug 18 '14 at 17:07
• $S(m)=S(m-2)+(m^2+(m-1)^2),$ right? then $S(m)=S(1)+(m^2+(m-1)^2+\cdots+2^2).$ – Ehsan M. Kermani Aug 18 '14 at 17:27

$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)$$.
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}
$$T(n)-T(1)=\sum_{r=2}^{n}\log^2 r\\ T(n)=T(1)+\sum_{r=2}^{n}\log^2 r$$