3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the help. Kindly elaborate the part $ l\times (n+1-l^2) $? $\endgroup$ – anubhav Dec 4 '15 at 16:05
  • $\begingroup$ 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)$. $\endgroup$ – Servaes Dec 4 '15 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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