<s>[INST] Find a formula for $\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$ I need to find a clear formula (without summation) for the following sum:
$$\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$$
Well, the first few elements look like this:
$1,1,1,2,2,2,2,2,3,3,3,...$
In general, we have $(2^2-1^2)$ $1$'s, $(3^2-2^2)$ $2$'s etc.
Still I have absolutely no idea how to generalize it for $n$ first terms...
 [/INST] 
The following is valid for $n\geq 1$


\begin{align*}
\sum_{k=1}^{n}\lfloor\sqrt{k}\rfloor
=n\lfloor\sqrt{n}\rfloor
-\frac{1}{3}\lfloor\sqrt{n}\rfloor^3-\frac{1}{2}\lfloor\sqrt{n}\rfloor^2+\frac{5}{6}\lfloor\sqrt{n}\rfloor
\end{align*}

For convenient calculations we consider two aspects:

*

*We introduce a variable $a=\lfloor\sqrt{n}\rfloor$. So, we have
$$a\leq \sqrt{n} < a+1$$

*We use the Iverson Bracket notation, so we can replace the expression $\lfloor x\rfloor$ by
$$\lfloor x\rfloor=\sum_{j\geq 0}[1\leq j \leq x]$$

Special case: $n=a^2,a=\lfloor\sqrt{n}\rfloor$


We start the calculation by conveniently assuming $n=a^2$. We obtain
\begin{align*}
\sum_{k=1}^{n}\lfloor\sqrt{k}\rfloor&=\sum_{k=1}^n\sum_{j\geq 0}[1\leq j \leq \sqrt{k}][0\leq k \leq a^2]\\
&=\sum_{j=1}^{a}\sum_{k=1}^{n}[j^2\leq k \leq a^2]\\
&=\sum_{j=1}^{a}(a^2-j^2+1)\\
&=a^3-\frac{1}{6}a(a+1)(2a+1)+a\\
&=\frac{2}{3}a^3-\frac{1}{2}a^2+\frac{5}{6}a\tag{1}
\end{align*}


General case: $n\geq a^2,a=\lfloor\sqrt{n}\rfloor$


In the general case we let again $a=\lfloor\sqrt{n}\rfloor$ and have additionally to consider the terms for
$a^2< k \leq n$.
They are all equal to $a$, so they sum up to $$(n-a^2)a.$$ Adding this to (1) we get the general formula with $a=\lfloor \sqrt{n}\rfloor$


\begin{align*}
\sum_{k=1}^{n}\lfloor\sqrt{k}\rfloor&=na-\frac{1}{3}a^3-\frac{1}{2}a^2+\frac{5}{6}a\\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box
\end{align*}

Note: This approach can be found in  Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik
Note: I've also added here an answer for the general case $\sum_{k=1}^n\lfloor\sqrt[p]{k}\rfloor$ with $p\geq 1$.
</s>