Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.