# Splitting summations?

From CLRS Introduction to Algorithms, Appendix A, page 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 &= \sum_{k=1}^{n/2} k + \sum_{k=n/2 + 1}^{n} k\\ &\geq \sum_{k=1}^{n/2} 0 + \sum_{k=n/2 + 1}^{n} (n/2)\\ &= (n/2)^2\\ &= \Omega(n^2)\,\end{align*}

I get step 1, that makes sense, but I didn't understand step 2 where they have replaced $$k$$ with $$0$$ in one part and $$k$$ with $$n/2$$ in the other. Why did they do this?

Thanks!

You can adapt this for example to show that the sum of $$k^5$$ for 1 ≤ k ≤ n is $$O(n^6)$$: You have n/2 terms each at least $$n^5/32$$, for a total of $$n^6/64 = O(n^6)$$. Or a lower bound for n!, where you have a product including n/2 terms each larger than n/2, so n! > $$(n/2)^{n/2}$$.