Calculate the sum of $\left\lfloor \sqrt{k} \right\rfloor$

Question

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.

Answer 1

The sum can be calculated as follows:

$$ \sum_{k=1}^{n^2} \lfloor \sqrt k \rfloor = 1 + 1 + 1 + \overbrace{2 + .. + 2}^{5 \space \text{terms}}+ \overbrace{3 + .. + 3}^{7 \space \text{terms}} + \overbrace{4 + .. + 4}^{9 \space \text{terms}} + .. + n $$

That reduces to: $$ 3 \times 1 + 5 \times 2 + 7 \times 4 + .. + (2n-1) \times (n-1) + n $$

The above sum is: $$ n + \sum_{k=1}^{n-1} (2n+1)\times n = \frac{n(4 n^2 - 3n + 5)}{6} $$

Which is gotten from the OEIS found by @lulu. I used the method given in the proof at the OEIS (given by J. M. Bergot), with insight from @Thomas Andrews and I believe the last equality is straightforward to prove by induction.

Answer 2

Put $$k= j^2+i$$ so that$j,i$ shall span $$ k \in \left[ {1,n^2 } \right]\quad \Rightarrow \quad \left\{ \begin{array}{l} j \in \left[ {1,n} \right] \\ i \in \left[ {0,\left( {j + 1} \right)^2 - j^2 } \right) = \left[ {0,2j} \right] \\ \end{array} \right. $$ and clearly it is $$ \left\lfloor {\sqrt k } \right\rfloor = j $$ and then the sum becomes $$ \begin{array}{l} S(n) = \sum\limits_{k = 1}^{n^2 } {\left\lfloor {\sqrt k } \right\rfloor } = \sum\limits_{j = 1}^{n - 1} {\sum\limits_{i = 0}^{2j} j } + \sum\limits_{j = n}^n {\sum\limits_{i = 0}^0 j } = \\ = \sum\limits_{j = 1}^{n - 1} {j\sum\limits_{i = 0}^{2j} 1 } + \sum\limits_{j = n}^n {j\sum\limits_{i = 0}^0 1 } = \left( {\sum\limits_{j = 1}^{n - 1} {\left( {2j + 1} \right)j} } \right) + n = \left( {2\sum\limits_{j = 1}^{n - 1} {j^2 } + \sum\limits_{j = 1}^{n - 1} j } \right) + n = \\ = 2\frac{{n\left( {2n - 1} \right)\left( {n - 1} \right)}}{6} + \frac{{n\left( {n - 1} \right)}}{2} + n = \\ = \frac{{2n\left( {2n - 1} \right)\left( {n - 1} \right) + 3n\left( {n - 1} \right) + 6n}}{6} = \\ = \frac{{4n^3 - 3n^2 + 5n}}{6} \\ \end{array} $$

Answer 3

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}