n(n+1)/2 combinatorial proof (details in description) Find the number of $2$-lists $(, )$ we can form using the numbers $0,1,2,...,$ with $ < $.
a. Show that the number is $( + 1)/2$ by considering the number of $2$-lists $(, )$ in which $ > $ or $ < $.
b. Show that the answer is also $1 + 2 + ⋯ + $.
Note that, part (a) and (b) together proves
$\sum_{k=1}^n k= n(n+1)/2$
This is a homework question, I tried to think of a method but couldn't figure out how. Any hints?
Thanks.
 A: Hints: 


*

*How many ways can a subset of two elements be selected from a set with $n + 1$ elements?

*Let $S = \{0, 1, 2, 3, \ldots, n\}$.  How many two-element subsets of $S$ have largest element $k$, where $k$ is a positive integer?

A: a)  How many 2-lists $b \ne a$ are there total?  How many choices are there for $a$?  How many choices are there for $b$?  So how many choices are there total?  What proportion  have $a > b$ and what proportion have $b < a$?  So how many have $a < b$?  Did you get the answer $n(n+1)/2$?  Why or why not?
b) If $b = 0$ how many choices are there for $a$?  If $b = 1$ how many choices are there for $a$?  For $b = k$ how many choices are there for $a$?  What is the sum of all these choices?  Did you get the answer $1 + 2 + .... + n$?  Why or why not?
A: Each of the $ n+1 $elements can be paired with any of the n elements. I guess order does not matter here, which is why we divide by two.
Some more perspectives on this.


*

*It is the same as choosing $2$ elements from a set of $(n+1) $things.

*It is the same as the number of edges a graph of $n+1 $vertices has.
That sum in part (a) is S.
$ 2S = n(n+1)$
      $= n+1  + n+1  + n+1  ... + n+ 1 (n times)$

     $=(1+n) + (2+ n-1) + (3+ n-2) + ... +(n+1)$

     $=(1+2+3+....+n) + (n+n-1 + n-2 + ... +2+1)$

     $=2(1+2+3+....+n)$

This implies that $S = 1 +2 + 3 + ... + n$
