Selection Sort Summation Simplification I am trying to simplify the summation for selection sort. Starting out with:
$$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}1$$
I am able to get:
$$\sum_{i=0}^{n-1}n-i-1$$
However, I don't understand how to simplify this summation any further. I don't know if I should pull the n outside of the summation, and I don't know what to do about the $i$. I would appreciate any help and detailed steps in how one gets from one step
 A: You should write your expression as 
$$\sum_{i=0}^{n-1} \left( n-i-1\right)$$ to make clear that you are summing not just $n$ but also the $-i-1$ terms.
The $n$ inside the term being summed ummation sign is just a constant during the summation. The $i$ in the expression being summed is the summation index in the outer sum. So you get
$$n\sum_{i=0}^{n-1} \left( 1 \right) -\sum_{i=0}^{n-1} \left(  i\right) - \sum_{i=0}^{n-1} \left( 1 \right) = n^2 - \frac{(n-1)n}{2}- n = \frac{n^2-n}{2}$$ 
A: "Pulling outside" is generally done when you have the product of $2$ terms, such as
$$\sum_{k=0}^nak=a\sum_{k=0}^nk$$
When summing terms, however, you can split the summation into parts.  For this example
$$\sum_{i=0}^{n-1}(n-i-1)=\sum_{i=0}^{n-1}(n-1-i)=\sum_{i=0}^{n-1}(n-1)-\sum_{i=0}^{n-1}i$$
Now, for that first sum, since nothing inside the summation depends on $i$, it's just a simple multiplication.  The second summation is an arithmetic sequence that you're hopefully familiar with.
A: Another way
is to reverse the order of summation.
In
$\sum_{i=0}^{n-1}(n-i-1)$,
let $j = n-1-i$,
so $i = n-1-j$.
At $i=0$, $j=n-1$;
at $i=n-1$, $j = 0$.
Therefore
$\sum_{i=0}^{n-1}(n-i-1)
=\sum_{j=0}^{n-1}(n-(n-1-j)-1)
=\sum_{j=0}^{n-1}(j)
=\frac{n(n-1)}{2}
$.
A: Note that 
$$\sum_{i=1}^{N}\sum_{j=i}^{N}1=\sum_{j=1}^N\sum_{i=1}^j1=\sum_{i=1}^{N}\binom j1=\binom {N+1}2=\frac {(N+1)N}2$$
Hence
$$\begin{align}
\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}1&=\sum_{i=1}^{n}\sum_{j=i}^{n-1}1\\
&=\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}1\\
&=\binom n2=\frac{n(n-1)}2\qquad\blacksquare
\end{align}$$
