Evaluate $\sum_{k=1}^n\lfloor \sqrt{k} \rfloor$ I know that $\sum_{k=1}^m k^2 = \frac{m(m+1)(2m+1)}{6}$.
How can I use this fact to evaluate $\sum_{k=1}^n\lfloor \sqrt{k} \rfloor$ ?

For $1\le r<\lfloor\sqrt n\rfloor$, there are exactly $2r+1$ summands of size $r$, namely for $r^2\le k<(r+1)^2$. The remaining $n+1-\lfloor\sqrt n\rfloor^2$ summands are $\lfloor\sqrt n\rfloor$ each. Therefore, with $m:=\lfloor\sqrt n\rfloor$, 
$$\begin{align}\sum_{k=1}^n\lfloor\sqrt k\rfloor &= 2\sum_{r=1}^{m-1}r^2+\sum_{r=1}^{m-1}r+(n+1-m^2)m\\&=\frac{(m-1)m(2m-1)}{3}+\frac{(m-1)m}2+(n+1)m-m^3\\&=mn-\frac{m(m-1)(2m+5)}6.\end{align}$$
