$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?
If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?
asymptotics;recurrence relation;recursion
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*}$$