1
$\begingroup$

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?

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

$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)$$.

$\endgroup$
1
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.