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$ ?
Evaluate $\sum_{k=1}^n\lfloor \sqrt{k} \rfloor$
-
0The 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. – 2012-10-04
2 Answers
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}$
-
0For which values of m is this sum $\sum_{k=1}^n \lfloor \sqrt(k) \rfloor$ divisible by m? – 2012-10-05
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$.