What property of summation is used while solving this problem?

Question

Saw this problem on a website.
Can someone explain how the summation is split into summation of summation?
What property of summation was used here? $$ T(n) = \sum_{k=1}^n \lfloor \sqrt{k} \rfloor. $$ Therefore $$ \begin{align*} T(m^2-1) &= \sum_{k=1}^{m^2-1} \lfloor \sqrt{k} \rfloor \\ &= \sum_{r=1}^{m-1} \sum_{\ell=r^2}^{(r+1)^2-1} \lfloor \sqrt{\ell} \rfloor \\ &= \sum_{r=1}^{m-1} \sum_{\ell=r^2}^{(r+1)^2-1} r \end{align*} $$

Answer 1

So, the first summation indexes from $1$ to $m^2-1$. The next line simply breaks that summation into chunks.

The left Summation indexes from $1$ to $m-1$ while the second summation will take that index and sum up to one less than the next number squared.

So, instead of one summation indexing $1,2,3,4,\dots m^2-1$, it is multiple summations. $$\Sigma_1^3 +\Sigma_4^8 +\Sigma_9^{15} +\Sigma_{16}^{24} +\dots +\Sigma_{(m-1)^2}^{m^2-1}$$

See how the next Summation always picks up where the previous one left off?

EDIT: An example of another summation splitting up.

$$\text{Sum of first n numbers}=\sum_{i=1}^{n}i=\sum_{i=1}^{\frac{n}{2}}\sum_{j=2i-1}^{2i}j$$

So, for $n=6$ instead of $\sum\limits_{i=1}^6i$ it is $$\sum\limits_{j=1}^2j+\sum\limits_{j=3}^4j+\sum\limits_{j=5}^6j$$

It's kind of a dumb example because I'm not all that clever.

Answer 2

Both the single sum $\displaystyle \sum_{\ell=1}^{m^2-1}$ and the nested sum $\displaystyle \sum_{r=1}^{m-1} \sum_{\ell=r^2}^{(r+1)^2-1}$ run over the same set of values:

• for $r=1$, $\ell$ runs from $1^2 = 1$ to $2^2-1 = 3$;
• for $r=2$, $\ell$ runs from $2^2 = 4$ to $3^2-1 = 8$;
• for $r=3$, $\ell$ runs from $3^2 = 9$ to $4^2-1 = 15$;
• ...
• for $r=m-1$, $\ell$ runs from $(m-1)^2$ to $m^2-1$.