<s>[INST] 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.
 [/INST] 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}
$$
</s>