# Sum of consecutive n integers

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

-
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
There is a proof without words of this fact. –  Marc van Leeuwen Jun 7 at 18:32

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

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

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

-

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

-
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