A Combinatorial Proof of the Summation Identity (i=1,i->n,i) = n(n+1)/2 http://img.skitch.com/20091012-mt5p22p1fxi3s1y32wqid49pwm.png http://img.skitch.com/200

A Combinatorial Proof of the Summation Identity (i=1,i->n,i) = n(n+1)/2 http://img.skitch.com/20091012-mt5p22p1fxi3s1y32wqid49pwm.png http://img.skitch.com/20091012-mt5p22p1fxi3s1y32wqid49pwm.pn... Zachary Burt, University of Chicago, 2007 Assume n people are in a room and they each shake hands with every other person. This constitutes n(n-1)/2 handshakes: each person shakes hands with every other person. The number is divided by two to account for double-counting the handshakes. The sum of handshakes can alternatively be computed by summing the number of unique handshakes made by each person: person 1 shakes n-1 hands, person 2 shakes n-2 hands (for he has already shaken hands with the first person), and so forth, until person n-1 shakes only one hand: person n has already shaken hands with everyone else. This can be expressed as: n-1 + n-2 + n-3 + ... + 1, or, through the commutative property of addition, 1 + 2 + .. + n-2 + n-1. This is conveniently expressed as the summation (i=1,i->n-1,i). We know that the summation (i=1,i->n-1,i) is equivalent to the expression n(n-1)/2. If we replace n-1 with n, this is the same as saying (i=1,i->n,i) = n(n+1)/2. QED.