Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
There is such a thing as "coincidence", you know... –  Arturo Magidin May 31 '12 at 19:58
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$ ... –  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

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.