<s>[INST] Solution for recurrence $T(n+1) = T(n) + \lfloor \sqrt{n+1}\rfloor $ ould someone please give me an idea as to how the solve the following. 
$$T(1) = 1$$
$$T(n+1) = T(n) + \lfloor\sqrt{n+1}\rfloor$$
I converted the recurrence to $T(n) = T(n-1) + \lfloor\sqrt{n}\rfloor$ and then tried to solve it using the method taught in the "linear recurrences solving from Mathematics for computer science course" at MIT and got the solution as $T(n) = n^\left(3/2\right) + 1$.
But the page I found this problem in asks for $T(n^2)$ and gives the answer as $\frac n6\left(4n^2 - 3n + 5\right)$, which I'm not able to derive.
Can someone please help me solve this recurrence?
Thanks 
 [/INST] When $n=1$, it is straightforward to see $T(1) = 1 = \frac{1}{6}(4 \times 1^2 - 3\times 1 + 5)$.
Assume $T(n^2) = \frac{n}{6}(4 n^2 - 3n + 5)$.
For $m = n^2, n^2+1, \ldots , (n+1)^2-2$, we have
$$T(m+1)-T(m) = \lfloor \sqrt{m+1} \rfloor = n$$
Summing up this relation over these $2n$ values of $m$ we have
$$T((n+1)^2 - 1) - T(n^2) = 2n^2$$
Therefore
$$T((n+1)^2) = T((n+1)^2 - 1) + (n+1) = T(n^2) + 2n^2 + n + 1$$
$$T((n+1)^2) = \frac{n}{6}(4 n^2 - 3n + 5) + 2n^2 + n + 1 = \frac{n+1}{6}(4 (n+1)^2 - 3(n+1) + 5)$$
</s>