How Splitting Summation method works I'm reading Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, Appendix&nbsp;A, page&nbsp;1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example,

$$\begin{align*}
\sum_{k=1}^{n} k &amp;= \sum_{k=1}^{n/2} k + \sum_{k=n/2 + 1}^{n} k\\
&amp;\geq \sum_{k=1}^{n/2} 0 + \sum_{k=n/2 + 1}^{n} (n/2)\\
&amp;= (n/2)^2\\
&amp;= \Omega(n^2)\,\end{align*}$$

I didn't understand step 2 where they have replaced $k$ with $0$ in one part and $k$ with $n/2$ in other. How does this method work? Can anybody explain?
$$\begin{align*}
55 = 1 + 2 + \dots + 10 &amp;= (1 + 2 + 3 + 4 + 5) + (6 + 7 + 8 + 9 + 10)\\
&amp;\color{red}{\geq} (0 + 0 + 0 + 0 + 0) + (5 + 5 + 5 + 5 + 5) \\
&amp;= (10/2)(10/2) = 25\,.\end{align*}$$

If you're wondering how to come up with such substitutions, there's no general method: this is one of the creative things you have to do to produce mathematical proofs.