Closed form of $\sum_{i=0}^{n-2}\sum_{i+1}^{n-1}1$ I should calculate the count of key comparisons from an algorithm. I create the sum formula but now I don’t know, how to dissolve this.
The sum looks like: 
$$
\eqalign{
\sum_{i=0}^{n-2}\sum_{i+1}^{n-1}1
}
$$
It would be nice, if someone could give me some tipps.
I knew that the second step must be: $ \sum_{i=0}^{n-2}(n-1-i) $
Greet.
 A: $$
\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}1 =
\sum_{i=0}^{n-2}((n-1)-(i+1)+1) =
\sum_{i=0}^{n-2}(n-1-i) =
\sum_{k=1}^{n-1}k = \frac{n(n-1)}{2}
$$
A: Let us start from your expression $ \sum_{i=0}^{n-2}(n-1-i) $.
Look at this in detail, starting at $i=0$. When $i=0$, we have $n-1-i=n-1$. Look next at $i=1$. We get $n-1-i=n-2$. Continue. We get in turn $n-3$, $n-4$, and so on. At the end, when $i=n-2$, we have $n-1-i=1$.
So we are looking at the sum
$$(n-1)+(n-2)+\cdots+1,$$
which will look more familiar if we write it as
$$1+2+\cdots+(n-1),$$
the sum of the first $n-1$ positive integers.
I assume you know the expression $\dfrac{m(m+1)}{2}$ for the sum of the first $m$ positive integers. The sum of the first $n-1$ positive integers is therefore
$$\frac{(n-1)(n)}{2}.$$
Comment: The first step, which is to show that 
$$\sum_{i+1}^{n-1} 1=n-1-i,$$ 
is simple, but it is all too easy to get the wrong answer. We are adding together $1$'s. How many $1$'s?  Just as many as there are integers from $i+1$ to $n-1$, inclusive.  Maybe you can see immediately that there are $(n-1)-(i+1)+1$ such integers, which simplifies to $n-1-i$.  But it is possible to get the count wrong by $1$.  For concreteness, how many integers are there from $5$ to $7$, inclusive? By a direct count, we are talking about the numbers  $5$, $6$, and $7$, so there are $3$ of them. Note that $7-5=2$, so simple subtraction undercounts by $1$.
A: It is near $\frac{n^2}{2}$.  Also if your 'second step' is correct then you distribute that into three sums.
