2

$$ 1 + 2 + \cdots + n = \binom {n+1} 2 $$ Please give me a help with combinational proof for this formula. Greetings for everybody and thanks in advance.

Michael Hardy
  • 1
user180834
  • 1,453

3 Answers3

4

You have $n+1$ people numbered $1,2, \ldots, (n+1)$.

Right hand side gives explicitly number of ways of choosing a pair of $2$ people from them.

LHS counts the same thing in the following way: you first decide on what the bigger number will be ($2, 3, 4, \ldots n+1$) and then you pick the second person from the people with lower numbers in, respectively, $1, 2, 3, \ldots n$ possible ways

Henry
  • 157,058
mm-aops
  • 4,195
3

Label $n+1$ objects as $1,...,n+1$. We will count the number of ways to choose $2$ objects out of these $n+1$ objects.

If we choose object $1$, there are $n$ ways to choose the next object. If we don't choose object $1$ but choose object $2$, there are $n-1$ ways to choose the next object. Hence there are $n+(n-1)+...+1$ ways to choose $2$ objects out of $n+1$ objects.

please delete me
  • 3,220
  • @Slade: "The first object" could have meant the initial choice rather than the earliest in an ordering. In any case Jasper Loy has edited the ambiguity away – Henry Oct 06 '14 at 21:07
3

As given by Mariano Suarez-Alvarez on this question on mathoverflow: (https://mathoverflow.net/questions/8846/proofs-without-words)

A proof of the identity $$1+2+\cdots + (n-1) = \binom{n}{2}$$

alt text

It shows that the yellow dots (which are the sum from 1 to $n-1$) can be put in a one-to-one correspondence with the pairs of blue dots, which are $n \choose 2$

P.S.

I have posted this as an answer and marked it community wiki, if it is preferable to just post the link to the mathoverflow answer in the comment I'll delete it!

P.P.S.

Should comment to say that I've put the answer on this site?

Community
  • 1
Ant
  • 21,098