Why is $\sum_{i=1}^{n}\sum_{j=i+1}^{n}1=n*(n-1)/2$?

Question

This summation came up because I wanted to calculate the number of terms in this set $$\{(i,j) | i > j; i,j = 1,...n\}$$

The summation is equivalent to the number of terms right?

Answer 1

$$\sum_{j=i+1}^n1=n-(i+1)+1=n-i$$

$$\sum_{i=1}^n(n-i)=\sum_{k=1}^{n-1}k=?$$ setting $n-i=k$

Answer 2

Let $A=\{(i,j) | i > j; i,j = 1,...n\}$, $B=\{(i,j) | i < j; i,j = 1,...n\}$ and $C=\{(i,j) | i = j; i,j = 1,...n\}$.

$A$, $B$ and $C$ are mutually disjoint and $A\cup B\cup C=\{(i,j) | i,j = 1,...n\}$.

By symmetry, We have $|A|=|B|$.

\begin{align*} |A|+|B|+|C|&=|\{(i,j) | i,j = 1,...n\}|\\ 2|A|+n&=n^2\\ |A|&=\frac{n^2-n}{2} \end{align*}

Answer 3

Just change the order of your summation: $$\sum_{i=1}^n \sum_{j=i+1}^n 1= \sum_{j=2}^n \sum_{i=1}^{j-1} 1 = \sum_{j=2}^n {(j-1)}=\sum_{j=1}^{n-1}j=\frac{n(n-1)}{2}$$

Answer 4

Your formula is just compute the number of ways to take two distinct numbers from $\{1,2,\ldots,n\}$, which is counted by binomial coefficient ${n\choose 2}=\frac{(n-1)n}{2}$.

Answer 5

Geometric answer to counting the number of terms in the set $$ U = \{ (i,j) : i > j, i,j = 1 \dots n \} $$ Mark the locations $(i,j)$ for $i=1\dots n-1$,$j=1 \dots n$. Notice that $U$ occupies half of the marked locations and that there are $n(n-1)$ locations marked.