# How Splitting Summation method works

I'm reading Cormen, Leiserson, Rivest and Stein, 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 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?

• In the second line, notice that it starts with $\ge$. – Rick Decker Dec 23 '15 at 17:36
• what book is CLRS? – miracle173 Dec 23 '15 at 22:57
• @miracle173 Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, MIT Press. This is actually a pretty standard abbreviation in the computer science community: if you Google for "CLRS", all the top hits refer to the right thing. (I'm not criticizing you for not Googling; just presenting evidence why using the abbreviation isn't crazy.) – David Richerby Dec 23 '15 at 23:11
• @DavidRicherby: You are right but maybe the result is a different if you google in five years or if you use duckduckgo or if you live in Kazakhstan – miracle173 Dec 23 '15 at 23:29
• @miracle173, I very much doubt that. – vonbrand Dec 30 '15 at 19:43

\begin{align*} 55 = 1 + 2 + \dots + 10 &= (1 + 2 + 3 + 4 + 5) + (6 + 7 + 8 + 9 + 10)\\ &\color{red}{\geq} (0 + 0 + 0 + 0 + 0) + (5 + 5 + 5 + 5 + 5) \\ &= (10/2)(10/2) = 25\,.\end{align*}