Calculate the sum of $\left\lfloor \sqrt{k} \right\rfloor$ 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.
 A: 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.
A: 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}
A: 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}
$$
