<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] Hint in the form of an example:  If you start the sum at $0$, you can write
$$\begin{align}
\lfloor\sqrt0 \rfloor+\lfloor\sqrt1 \rfloor+\lfloor\sqrt2 \rfloor+\cdots+\lfloor\sqrt{11} \rfloor&=0+1+1+1+2+2+2+2+2+3+3+3\\
&=3+3+3+3+3+3+3+3+3+3+3+3\\
&\quad-1-1-1-1-1-1-1-1-1\\
&\quad-1-1-1-1\\
&\quad-1\\
&=12\cdot3-(1+4+9)\\
&=(11+1)\lfloor\sqrt{11}\rfloor-(1^2+2^2+\cdots+\lfloor\sqrt{11}\rfloor^2)
\end{align}$$
Remark:  The main reason for including the unnecessary term $0$ is that it makes it easier to describe the pattern of what's being subtracted.  (Note, there are not $11$ terms in $1^2+2^2+\cdots+\lfloor\sqrt{11}\rfloor^2$, but only $\lfloor\sqrt{11}\rfloor=3$ terms.)  Properly understood, the pattern explains the generalization to $\lfloor\sqrt[p]n\rfloor$ in Claude Leibovici's answer.
</s>