Combinatorial proof of sum of numbers Does anyone have any insight on showing that $\sum_{i=1}^n i = {n+1\choose 2}$, through a combinatorial argument (i.e., not an algebraic argument)?
 A: *

*We will make two choices.  First we will chose a number $i$ from $\{1,\ldots, n\}$ and  put down a row of $i$ identical objects.  Then we will split the row into at most two parts.
Clearly, for each $i$ the row can be split in exactly $i$ ways.  So the number of possible ways of doing this is $\sum_{i=1}^n i$.

*But this is the same as taking a row of $n$ objects, inserting two dividers, say to the right of objects $k_1$ and $k_2$, discarding all the objects to the right of the rightmost divider, and considering the remaining row of objects as being divided in two by the left divider.  And there are $n+1\choose 2$ ways to insert the two dividers.
A: See the top-voted proof without words at MathOverflow.  This proof was discovered by Loren Larson, professor emeritus at St. Olaf College. He included it along with a number of other, more standard, proofs, in "A Discrete Look at $1+2+...+n$," published in 1985 in The College Mathematics Journal (vol. 16, no. 5, pp. 369-382).
A: Here is a very simple combinatorial proof which uses the fact:
$$\sum_{k=r}^{n} {k \choose r} = {n+1 \choose r+1}$$
Proof:
Consider the numbers $1,2,3,...,n,(n+1)$.
Note that we can select $(r+1)$ numbers from these $(n+1)$ numbers in ${n+1\choose r+1}$ ways. 
But note that every choice of $(r+1)$ elements must have a largest element, so we can as well pick this largest element $t$ and pick the remaining $r$ numbers from the the set of all numbers less than $t$. But $t$ can range from $(r+1)$ to $(n+1)$, and for each choice of $t$ we have to select the remaining $r$ elements in ${t-1 \choose r}$ ways, so we have
$$\sum_{t=r+1}^{n+1} {t-1 \choose r} = \sum_{k=r}^{n} {k \choose r} = {n+1 \choose r+1}$$
Now our original problem simply becomes
$$\sum_{k=1}^{n} {k \choose 1} = \sum_{k=1}^{n} k = {n+1 \choose 2}$$
And we are done.
A: There is a way to see this inductively. Suppose you knew this formula up till $n-1$. Then, $n + 1$ choose $2$ is equal to $n$ choose $2$ plus the number of ways to choose a pair of distinct elements from $\{1,\cdots, n + 1\}$ such that one of them is the 'new' element $n+1$. This is equal to $n$ choose $1$, i.e. $n$, and so the difference between $n+1$ choose $2$ and $n$ choose $2$ must be $n$.
