Skip to main content
3 of 3
added 252 characters in body

If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$
$T(1)=1$

The value of $T(m^2)$ for m ≥ 1 is?

Clearly you cannot apply master theorem because it is not of the form $T(n)=aT(\frac{n}{b})+f(n)$

So I tried Back Substitution:
$T(n)=T(n-1)+\lfloor\sqrt{n}\rfloor$
$T(n-1)=T(n-2)+\lfloor\sqrt{n-1}\rfloor$
therefore,
$T(n)=T(n-2)+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
$T(n)=T(n-3)+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
.
.
$T(n)=T(n-(n-1))+...T(n-k)+\lfloor\sqrt{n-(k-1)}\rfloor+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
.
.
$T(n)=T(1)+...T(n-k)+\lfloor\sqrt{n-(k-1)}\rfloor+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
$T(n)=T(1)+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$

I'm stuck up here and the answer is given as -

$T(m^2)=\frac{m}{6}(4m^2 - 3m + 5)$

how to solve and reach the answer?