formula for $\sum_{k=0}^{m} \lfloor{\sqrt{k}}\rfloor$ when m is a positive integer

Question

I am stuck with deriving a formula for $\sum_{k=0}^{m} \lfloor{\sqrt{k}}\rfloor$ when m is a positive integer?

Answer 1

Hint: $(n+1)^2-n^2=2n+1$. For $a^2\le k<(a+1)^2$, $\lfloor\sqrt k\rfloor=a$.

Answer 2

Suppose that $n^2\le k<(n+1)^2$; then $\lfloor\sqrt{k}\rfloor=n$. There are $2n+1$ integers $k$ in this interval, so if $m\ge n^2+2n$, they contribute $n(2n+1)$ to the total. Thus, if $n^2\le m<(n+1)^2$,

$$\sum_{k=0}^m\left\lfloor\sqrt{k}\right\rfloor=\sum_{k=1}^{n-1}\left(2k^2+k\right)+\left(m-n^2+1\right)n\;.\tag{1}$$

You can use the standard formulas for the sums of consecutive squares and consecutive integers to simplify the summation on the righthand side of $(1)$, and of course $n=\lfloor\sqrt{m}\rfloor$, so you can simplify the righthand side to a function of $m$ that does not contain a summation.