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.

It is well-known that $1+2+3+4+...+n= \frac{n(n+1)}{2}$, this formula can be found using simple arithmetic progression. But the sum also can be found by using ${n+1 \choose 2}$, which is n+1 choose 2. Can anyone explain the relationship between the binomial coefficient and the sum of consecutive integers? I found the binomial coefficient formula at wikipedia: http://en.wikipedia.org/wiki/Triangular_number

share|improve this question
2  
Not your topic, but it might interest you that this can generalized: $\sum_{k=r}^{n}\binom{k}{r}=\binom{n+1}{r+1}$. It can be proved quite easily by induction. –  drhab Jun 7 at 7:54
1  
There is a proof without words of this fact. –  Marc van Leeuwen Jun 7 at 18:32

4 Answers 4

up vote 6 down vote accepted

I think this is a better way that justifies the name Triangular Number. Consider the (right) triangular arrangement with $n$ rows and columns, the rows indexed by $i = 1, 2, \ldots n$, and the columns indexed by $0, 1, \ldots n - 1$: $$\begin{matrix}1 \\ 2 \\ 3 \\ \vdots \\ n\\ \ \end{matrix}\left| \begin{matrix} *&\\ *& *\\ *& *& *&\\ \vdots& \vdots& \vdots& \ddots\\ *& *& *& \ldots & *\\ \hline 0 & 1 & 2 & \ldots & n-1 \end{matrix}\right.$$

The total number of objects is obviously $1 + 2 + \ldots + n$ (the sum of the number of objects in each row). However, observe that each object corresponds to a unique pair of the form $(i, j)$ with $j < i$, where $i$ is the row and $j$ is the column occupied by the object. Thus the number of objects is the number of such pairs, which is the number of distinct pairs of the $n + 1$ numbers $0, 1, \ldots, n + 1$, and that is $\binom {n + 1} 2$.

share|improve this answer
    
is there some minor mistake in the image? the last row is not properly aligned with the above columns –  Dave Clifford Jun 7 at 8:33
    
@DaveClifford Thanks, I fixed it. –  M. Vinay Jun 7 at 8:36
    
No, I should be the person who should thank you :) Nice interpretation! –  Dave Clifford Jun 7 at 8:38
    
still not entirely correct. the last row should be 0 1 2 ... n-1 –  Egon Jun 7 at 22:16
    
ya, but that is pretty trivial, everyone should be able to correct it themselves –  Dave Clifford Jun 8 at 1:40

If all $n + 1$ people at a party shake hands with each other such that every two people shake hands exactly once, how many handshakes are there?

Let's count the number of handshakes in two different ways:

  1. The first person shakes hands with the remaining $n$ people. The second person shook hands with the first already, so he shakes hands with the remaining $n - 1$ people. And continuing in this manner, the last-but-one person shakes hands with the last $1$ person. The last person shakes hands with none. So the number of handshakes is $n + (n - 1) + \ldots + 1$ = $1 + 2 + \ldots + n$.
  2. The number of handshakes is the number of ways of selecting a pair of people from $n + 1$ people (because every possible pair shakes hands exactly once), that is $\binom {n + 1} 2$.

Since the number of handshakes is the same no matter how you count it (correctly) $$1 + 2 + \ldots n = \binom {n + 1} 2$$

share|improve this answer
    
This is basically the handshaking lemma or degree sum formula (en.wikipedia.org/wiki/Handshaking_lemma) applied to the complete graph on $n$ vertices. –  M. Vinay Jun 7 at 7:51
    
This is very cool! Great post! I like your view on counting more than mine, more intuitive! –  DanZimm Jun 7 at 7:53
    
@DanZimm Thanks. Can't help thinking that way, I'm a graph theorist :P –  M. Vinay Jun 7 at 7:54
    
And a very wise one at that, I've seen you answering posts recently and you seem to have a vast spectrum of knowledge :D –  DanZimm Jun 7 at 7:56

When you look at $n+1$ objects then lets try to manually count how many ways we can choose $2$ objects.

First we can count the $n$ pairs of consecutive objects, then then $n-1$ pairs that have one object in between and so on until we have the $1$ pair with $n-1$ objects in between. Thus here we can see that the number of ways to choose two objects is $n + n-1 + n-2 + \cdots + 2 + 1$ which is exactly what $\sum_{k=1}^n k$ is. Thus we come to the conclusion that $\sum_{k=1}^n k = \binom{n+1}{k}$.

share|improve this answer

HINT:

If you start choosing $2$ elements from $n+1,$ say $a_i(1\le I\le n+1)$

first choose $1$ element (say $a_0$), the other can be chosen from the rest $n:\{a_1,a_2,\cdots,a_{n-1},a_n\}$ elements

for the next $a_1$ element, the other can be chosen from the rest $n-2:\{a_2,\cdots,a_{n-1},a_n\}$ elements as $a_0a_1$ has already been chosen as the order immaterial here

So on

share|improve this answer
1  
So the relationship is purely algebraic? I thought there is some relationship between the summation and the counting. –  Dave Clifford Jun 7 at 7:46
    
@DaveClifford, I believe so –  lab bhattacharjee Jun 7 at 7:47

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.