# 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$ ?

-
Why do you think knowing that will be useful? –  Chris Eagle Oct 4 '12 at 18:26
It may not be useful at all but I was hoping it might be! –  H153 Oct 4 '12 at 18:28
The nicest formula is for $m=w^2-1$. Write out the numbers, for $w$ small but not too small, like $w=6$. We get $3$ $1$'s, $5$ $2$'s, $7$ $3$'s, $9$ $4$'s, $11$ $5$'s. Out of this you can make a formula. And yes, sum of squares will be useful. –  André Nicolas Oct 4 '12 at 18:31

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}

-
For which values of m is this sum $\sum_{k=1}^n \lfloor \sqrt(k) \rfloor$ divisible by m? –  H153 Oct 5 '12 at 8:08

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$.

-