Question regarding simple transformation in chapter 3.5 (Floor/Ceiling Sums) of Concrete Mathematics

Question

The chapter starts with the following sum of floors whose closed form is intended to be found:

$ \sum_{0 \leq k < n}{ \lfloor \sqrt{k} \rfloor } $

The authors expand the term by introducing a new variable $ m = \lfloor \sqrt{k} \rfloor $. Then, at first, they do three trivial transformations, where the brackets used are Iverson Brackets:

$ = \sum_{k, m \geq 0}{m[k < n][m = \lfloor \sqrt{k} \rfloor]} $

$ = \sum_{k, m \geq 0}{m[k < n][m \leq \sqrt{k} < m+1]} $

$ = \sum_{k, m \geq 0}{m[k < n][m^2 \leq k < (m+1)^2]} $

The next line is what I have problems with:

$ = \sum_{k, m \geq 0}{m[m^2 \leq k < (m+1)^2 \leq n]} \\ \qquad + \sum_{k, m \geq 0}{m[m^2 \leq k < n < (m+1)^2]} $

Although I have a vague idea why they do it like this, I'd rather be able to thoroughly understand the next reshaping.

If the line above is just trivially following an identity that I haven't heard of before, could you please refer me to resources that explain how and why I simply can move $ [k < n] $ into $ [m^2 \leq k < (m+1)^2] $ creating another sum? If it is not simply derived by some rule, could you come up with an intuitive explanation for this?

Answer 1

The expression \begin{align*} \sum_{k,m\geq 0}m[k<n][m^2\leq k<(m+1)^2] \end{align*} tells us to sum over all $k,m$ especially with $k<n$ and $k<(m+1)^2$. This is split in the next line into two different cases, namely either $$(m+1)^2\leq n\qquad\text{or}\qquad n<(m+1)^2$$

Since this covers all possibilities of $k,m$ and $n$, the next line holds.

\begin{align*} &\sum_{k, m \geq 0}{m[m^2 \leq \color{blue}{k < (m+1)^2 \leq n]}} \\ &\qquad + \sum_{k, m \geq 0}{m[m^2 \leq\color{blue}{ k < n < (m+1)^2}]} \end{align*}