<s>[INST] 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$ ?
 [/INST] When $i^2\leq k<(i+1)^2-1$, $\lfloor \sqrt{k} \rfloor=i$.
So $\lfloor \sqrt{k} \rfloor$ takes $2i+1$ times the value $i$. 
If $m^2 \leq n < (m+1)^2$, $\sum_{k=1}^n \lfloor \sqrt{k} \rfloor= (\sum_{k=1}^{m^2-1} \lfloor \sqrt{k} \rfloor)+ (\sum_{k=m^2}^n \lfloor \sqrt{k} \rfloor)=
(\sum_{i=1}^{m-1} (2i+1) \times i) + (n-m^2+1) \times m=\sum_{i=1}^{m-1}2i^2+\sum_{i=1}^{m-1}i +(n-m^2+1)m$.
So the sum equals $m(m-1)(2m-1)/3+m(m-1)/2+(n-m^2+1)m$.
</s>