I'm trying to calculate for $n\in \mathbb{N}$ the following sum :
$\sum_{k=1}^{n^2}\left\lfloor \sqrt{k} \right\rfloor$.
I tried putting in the first terms, which gave me
$\sum_{k=1}^{n^2}\left\lfloor \sqrt{k} \right\rfloor=(1+2+3+\cdots+n)+\left\lfloor \sqrt{2} \right\rfloor+\left\lfloor \sqrt{3} \right\rfloor+\left\lfloor \sqrt{5} \right\rfloor+\cdots+\left\lfloor \sqrt{n^2-1} \right\rfloor$
$\iff \sum_{k=1}^{n^2}\left\lfloor \sqrt{k} \right\rfloor=\frac{n(n+1)}{2}+\left\lfloor \sqrt{2} \right\rfloor+\left\lfloor \sqrt{3} \right\rfloor+\left\lfloor \sqrt{5} \right\rfloor+\cdots+\left\lfloor \sqrt{n^2-1} \right\rfloor$.
I've been trying to somehow find a pattern between the different integer parts of the irrational numbers just like I did with the integers but I fail to success.
Is there a trick to use here or is my take wrong ?
Thank you.
Best Answer
Here's a proof using the benefits of the Iverson bracket:
\begin{align} \sum_{k=1}^{n^2}\lfloor\sqrt{k}\rfloor &= \sum_{k=1}^{n^2}\sum_{j=1}^n[\;j \le \sqrt{k}\;]\\ &= \sum_{j=1}^n \sum_{k=1}^{n^2}[\;j \le \sqrt{k}\;]\\ &= \sum_{j=1}^n \sum_{k=1}^{n^2}[\;j^2 \le k\;]\\ &= \sum_{j=1}^n \sum_{k=j^2}^{n^2}1\\ &= \sum_{j=1}^n (n^2-j^2+1)\\ &= n^3 - \frac{1}{6}n(n+1)(2n+1)+n\\ &= \frac{1}{6}n(4n^2-3n+5) \end{align}