n(n+1)/2 combinatorial proof (details in description)

Question

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.

Answer 1

Hints:

1. How many ways can a subset of two elements be selected from a set with $n + 1$ elements?
2. 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?

Answer 2

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.

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

2. 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$

Answer 3

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?