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

Question

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.

Answer 1

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