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 
 A: First notice that $T(n)=1+[\sqrt{2}]+[\sqrt{3}]+...+[\sqrt{n}]$
The function $[\sqrt{n}]$ is piece-wise constant. So, let us divide the sum above into these pieces. 
We have that $[\sqrt{n}]=k$ when $k^2\leq n\leq k^2+2k$.
Therefore $T(n)=1\cdot(2\cdot 1+1)+2(2\cdot 2+1)+3\cdot(2\cdot 3+1)+...+[\sqrt{n}](n-[\sqrt{n}]+1)$
Hence $$T(n)=2\left(1^2+2^2+...+([\sqrt{n}]-1)^2\right)+\left(1+2+3+...+([\sqrt{n}]-1)\right)+[\sqrt{n}]\left(n-[\sqrt{n}]+1\right)$$
Use now the sum of consequtive squares and the sum of consecutive numbers formulas to finish it.
A: 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)$$
