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

Question

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

Answer 1

Your problem is that you're ignoring the floors. Make sure that you know what $\lfloor x \rfloor$ means.

It is not hard to check that $$ T(n) = \sum_{k=1}^n \lfloor \sqrt{k} \rfloor. $$ Therefore $$ \begin{align*} T(m^2-1) &= \sum_{k=1}^{m^2-1} \lfloor \sqrt{k} \rfloor \\ &= \sum_{r=1}^{m-1} \sum_{\ell=r^2}^{(r+1)^2-1} \lfloor \sqrt{\ell} \rfloor \\ &= \sum_{r=1}^{m-1} \sum_{\ell=r^2}^{(r+1)^2-1} r \\ &= \sum_{r=1}^{m-1} [(r+1)^2-r^2] r \\ &= \sum_{r=1}^{m-1} (2r+1)r \\ &= \sum_{r=1}^{m-1} 4\binom{r}{2} + 3\binom{r}{1} \\ &= 4\binom{m}{3} + 3\binom{m}{2}. \end{align*} $$ Therefore $$ \begin{align*} T(m^2) &= 4\binom{m}{3} + 3\binom{m}{2} + m \\ &= \frac{4m(m-1)(m-2)}{6} + \frac{3m(m-1)}{2} + m \\ &= \frac{(4m^3-12m^2+8m) + (9m^2-9m) + (6m)}{6} \\ &= \frac{4m^3-3m^2+5m}{6}. \end{align*} $$

Answer 2

For a slightly different way to look at his problem, consider your original equation, $$ T(n) = T(1)+\lfloor\sqrt2\rfloor+\lfloor\sqrt3\rfloor+\dotsb+\lfloor\sqrt n\rfloor $$ Now the key here is to group the terms with the same values of $\lfloor\sqrt k\rfloor$: $$\begin{align} T(n) &= (T(1)+\lfloor\sqrt2\rfloor+\lfloor\sqrt3\rfloor)\\ &+(\lfloor\sqrt4\rfloor+\lfloor\sqrt5\rfloor+\lfloor\sqrt6\rfloor+\lfloor\sqrt7\rfloor+\lfloor\sqrt8\rfloor)\\ &+(\lfloor\sqrt9\rfloor+\lfloor\sqrt{10}\rfloor+\lfloor\sqrt{11}\rfloor+\lfloor\sqrt{12}\rfloor+\lfloor\sqrt{13}\rfloor+\lfloor\sqrt{14}\rfloor+\lfloor\sqrt{15}\rfloor)\\ &+\dotsc \end{align}$$ and observe that each summand will have $2k+1$ terms, since the difference $(k+1)^2-k^2 = 2k+1$: $$ T(n) = (1\cdot3)+(2\cdot5)+(3\cdot 7)+(4\cdot 9)+\dotsb $$ so we'll have, with $n=m^2$ $$\begin{align} T(m^2) &= (1\cdot3)+(2\cdot5)+\dotsb+\left(\left\lfloor\sqrt{(m-1)^2}\right\rfloor+\dotsb+\left\lfloor\sqrt{m^2-1}\right\rfloor\right)+\left\lfloor\sqrt{m^2}\right\rfloor\\ &=\sum_{k=1}^{m-1}k(2k+1)+m =\sum_{k=1}^{m-1}(2k^2+k)+m\\ &=2\sum_{k=1}^{m-1}k^2+\sum_{k=1}^{m-1}k+m\\ &=2\frac{(m-1)(m)(2(m-1)+1)}{6}+\frac{(m-1)(m)}{2}+m\\ &=\frac{m}{6}(4m^2-3m+5) \end{align}$$ as required.