discrete mathematics - Find a formula for $sumlimits_{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...

Answer

Hint

We have
$$p\le\sqrt k< p+1\iff p^2\le k<(p+1)^2\Rightarrow \lfloor \sqrt{k} \rfloor=p$$
so

$$\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor=\sum\limits_{p=1}^{\lfloor \sqrt{n+1}\rfloor-1} \sum_{k=p^2}^{(p+1)^2-1}\lfloor \sqrt{k} \rfloor=\sum\limits_{p=1}^{\lfloor \sqrt{n+1}\rfloor-1}p(2p+1)$$
Now use the fact

$$\sum_{k=1}^n k=n(n+1)/2$$
and
$$\sum_{k=1}^n k^2=n(n+1)(2n+1)/6$$
to get the desired closed form.