What property of summation is used while solving this problem? 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*}
$$

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$.

