# Summation of Greatest Integer $\sum_{k=1}^{n} \left \lfloor{\sqrt{k}}\right \rfloor$

I want to know the concept behind summing up a Greatest Integer function like $\sum_{k=1}^{n} \left \lfloor{x}\right \rfloor$ can be evaluated by simply writing the series but something like $$\sum_{k=1}^{n} \left \lfloor{\sqrt{k}}\right \rfloor$$ This is creating problem by simply writing the series it came out to be $$S=1\times3 +2\times4+3\times5+4\times6+...$$ The sum of this can be written as $$\sum_{r=1}^{n} (r)(2r+1)$$ but then i am not able to relate $r$ and $k$ to each other.

For any given $m\geq0$, we have $\lfloor\sqrt{k}\rfloor=m$ if and only if $m^2\leq k<(m+1)^2$. So the number of times $m$ occours in the sum is $$(m+1)^2-m^2=2m+1.$$ Setting $\ell:=\lfloor\sqrt{n}\rfloor$ this indeed leads to the simplification you already found: $$\sum_{k=0}^n\lfloor\sqrt{k}\rfloor=\ell\cdot(n+1-\ell^2)+\sum_{m=0}^{\ell-1}m\cdot(2m+1),$$ where the term $\ell\cdot(n+1-\ell^2)$ comes from the fact that we're not summing over all integers $k$ for which $\lfloor\sqrt{k}\rfloor=\ell$, but just the first $n+1-\ell^2$ such integers. Now we can write the sum out as \begin{eqnarray*} \ell\cdot(n+1-\ell^2)+\sum_{m=0}^{\ell-1}m\cdot(2m+1) &=&\ell\cdot(n+1-\ell^2)+2\sum_{m=0}^{\ell-1}m^2+\sum_{m=0}^{\ell-1}m\\ &=&\ell\cdot(n+1-\ell^2)+\frac{1}{3}\cdot\ell(\ell-1)(2\ell-1)+\frac{1}{2}\ell(\ell-1)\\ &=&-\frac{1}{3}\ell^3-\frac{1}{2}\ell^2+\left(n+\frac{5}{6}\right)\ell\\ &=&n\ell-\frac{1}{6}\ell\left(\ell-1\right)\left(2\ell+5\right) \end{eqnarray*}
• Thanks for the help. Kindly elaborate the part $l\times (n+1-l^2)$? – anubhav Dec 4 '15 at 16:05
• Each value $m<\lfloor\sqrt{n}\rfloor$ is summed precisely $2m+1$ times, as explained in my answer. The last value $\ell=\lfloor\sqrt{n}\rfloor$ might be summed fewer times, depending on $n$. The number of times it is summed is precisely $n+1-\ell^2$, so this sums to $\ell\cdot(n+1-\ell^2)$. – Servaes Dec 4 '15 at 16:14