<s>[INST] Floor of Square Root Summation problem I have problem calculating the following summation:
$$
S = \sum_{j=1}^{k^2-1} \lfloor \sqrt{j}\rfloor.
$$
As far as I understand the mean of that summation it will be something like $$1+1+1+2+2+2+2+2+3+3+3+3+3+3+3+\cdots$$
and I suspect that the last summation number will be $(k-1)^2$, but I really can't find the pattern of the equal simpler summation.   
 [/INST] Let $\lfloor \sqrt{n} \rfloor = a$, then the following sum holds:
$$\sum_{0\le k < n} \lfloor \sqrt{k} \rfloor = (n+1)a - \frac{a^3}{3} -
    \frac{a^2}{2} - \frac{a}{6}.$$
(Edited.)
You might also enjoy the slightly more tricky sum:
$$\sum_{0\le k < n} \lfloor k^{1/3} \rfloor = nb - \frac{b^2}{4} - \frac{b^3}{2} - \frac{b^4}{4},$$
where this time $b =\lfloor n^{1/3} \rfloor$
One way to obtain these answers is to merely apply the summation identity that I mentioned here
</s>