<s>[INST] Concrete Mathematics Section 3.5: Floor / Ceiling sum manipulation Problem: To find the closed form of $\sum_{0 \le k \lt n}\lfloor \sqrt{k} \rfloor$
The text goes on solving as follows
$$
\begin{align}
\sum_{0 \le k \lt n}\lfloor \sqrt{k} \rfloor
&= \sum_{k,m \ge 0}m[k < n][m = \lfloor \sqrt{k} \rfloor]\\
&= \sum_{k,m \ge 0}m[k < n][m \le \sqrt{k} < m + 1]\\
&= \sum_{k,m \ge 0}m[k < n][m^2 \le k < (m + 1)^2]\\
&= \sum_{k,m \ge 0}m[m^2 \le k < (m + 1)^2 \le n] + \sum_{k,m \ge 0}m[m^2 \le k < n < (m + 1)^2]
\end{align}
$$
Let's assume that $n = a^2$ is a perfect square. Then the second sum is zsero and the first can be evaluated as
$$
\newcommand{\fallingfactorial}[1]{%
  ^{\underline{#1}}%
}
\begin{align}
\sum_{k,m \ge 0}m[m^2 \le k < (m + 1)^2 \le a^2]
&= \sum_{m \ge 0}m((m + 1)^2 - m^2)[m + 1 \le a]\\
&= \sum_{m \ge 0}m(2m + 1)[m < a]\\
&= \sum_{m \ge 0}(2m\fallingfactorial{2} + 3m\fallingfactorial{1})[m < a]\\
&= \sum_0^a (2m\fallingfactorial{2} + 3m\fallingfactorial{1}) \delta m\\
&= \frac{1}{6}(4a + 1)a(a - 1)
\end{align}
$$
The next part I don't understand
It says: In general we can let a = $\lfloor \sqrt{n} \rfloor$; then we merely need to add the term $a^2 \le k < n$, which are all equal to a, so they sum to $(n - a^2)a$. This gives the desired closed form,
$$
\sum_{0 \le k < n} \lfloor \sqrt{k} \rfloor = na - \frac{1}{3}a^3 - \frac{1}{2}a^2 - \frac{1}{6}a, \text{where } a = \lfloor \sqrt{n} \rfloor
$$
Why we are considering $a^2 \le k \lt n$, shouldn't we consider $a \le k \lt n$ as we have already calculated for $0 \le k \lt a$ before ?
 [/INST] We consider the second sum  in somewhat more detail which might help to clarify the situation.

We obtain
  \begin{align*}
\color{blue}{\sum_{k,m\geq 0}}&\color{blue}{m[m^2\leq k<n<(m+1)^2]}\tag{1}\\
&=\sum_{k\geq 0}a[a^2\leq   k<n<(a+1)^2]\tag{2}\\
&=\sum_{{k\geq 0}\atop{a^2\leq  k <n}}a\tag{3}\\
&=\sum_{a^2\leq  k <n}a=\sum_{k=a^2}^{n-1}a\tag{4}\\
&\color{blue}{=(n-a^2)a}
\end{align*}

Comment:


*

*In (1) we observe that if $n$ is fixed there is precisely one integer $m$ which fulfills the condition
$$[m^2\leq k<n<(m+1)^2]$$
So, we sum in fact only over $k$. 

*In (2) we sum over $k$ only and denote the single value $m$ with $a$. We have
$$m=a=\lfloor \sqrt n\rfloor$$
The condition $[\color{blue}{a^2\leq   k<n}<(a+1)^2]$ tells us that we have a non-zero contribution only if $a^2\leq k<n$.

*In (3) we rewrite the condition from (2) as index range.

*In (4) we do a small simplification.
</s>