3
$\begingroup$

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?

  • 0
    There *is* such a thing as "coincidence", you know...2012-05-31
  • 2
    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$ ...2012-05-31
  • 0
    @David: But how do you interpret the problem of counting the handshakes as a problem of choosing 2 out of $n+1$ possibilities?2012-05-31
  • 0
    @ArturoMagidin You have $n$ people. In how many ways can you choose two of them (to shake hands)? Am I off here?2012-05-31
  • 0
    @David: I just wasn't making the connection.2012-05-31
  • 0
    Have a look at the highest-rated answer here: http://mathoverflow.net/questions/8846/proofs-without-words2012-05-31

2 Answers 2

6

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

4

Look at this picture on mathoverflow:

https://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.