Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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