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

  • 1
    $\begingroup$ Why do you think knowing that will be useful? $\endgroup$ – Chris Eagle Oct 4 '12 at 18:26
  • $\begingroup$ It may not be useful at all but I was hoping it might be! $\endgroup$ – H153 Oct 4 '12 at 18:28
  • $\begingroup$ 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. $\endgroup$ – 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}$$

  • $\begingroup$ For which values of m is this sum $\sum_{k=1}^n \lfloor \sqrt(k) \rfloor$ divisible by m? $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.