# Relation between the sum of integers until n and the number of ways to choose 2 among n+1

On the one hand we have $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ and on the other hand, we count $\frac{(n+1)!}{2!(n+1-2)!} = \frac{n(n+1)}{2}$ ways to choose 2 items among n+1.

How can we explain that $1 + 2 + \cdots+ n$ is also the number of ways to choose 2 items among n+1?

-
There is such a thing as "coincidence", you know... –  Arturo Magidin May 31 '12 at 19:58
You can use induction. Think about the problem as the total number of handshakes made if $n$ people gather and everyone shakes everyone elses hand. With two people there is one handshake. If a third person arrives, this gives two more handshakes for a total of $1+2$ handshakes for three people (the third person shakes hands with the previous two). For four people, there would be three more handshakes for a total of $1+2+3$ ... –  David Mitra May 31 '12 at 19:59
@David: But how do you interpret the problem of counting the handshakes as a problem of choosing 2 out of $n+1$ possibilities? –  Arturo Magidin May 31 '12 at 20:01
@ArturoMagidin You have $n$ people. In how many ways can you choose two of them (to shake hands)? Am I off here? –  David Mitra May 31 '12 at 20:03
@David: I just wasn't making the connection. –  Arturo Magidin May 31 '12 at 20:05

Think of your $n+1$ items as being labeled from 1 to $n+1$. You need to make two choices if you're picking two elements: The one with the smaller label, and the one with the larger label. If you pick $n$ for the smaller label, there's only 1 choice for the larger. If you pick $n-1$ for the smaller, there's 2 choices for the larger, etc., all the way down to $n$ choices for the larger if you choose $1$ for the smaller. The total number of ways you can pick two elements is then the sum of the ways you can do it for each choice of smaller label, which is $1 + 2 + ... + n$.

-

Look at this picture on mathoverflow:

http://mathoverflow.net/questions/8846/proofs-without-words/8847#8847

The number of yellow circles is clearly $1+2+\dots + n$. The number of blue circles is $n+1$.

Each choice of a yellow circle corresponds to a choice of two blue circles.

-