# Handshakes and the young Gauss

If a group of n people meet, and everyone shakes hands with everyone else, how many handshakes occur?

I posed this problem to a friend, to see if she would give me the correct answer, which is n(n – 1) / 2. It’s easy to see why this formula is correct: every one of the n persons must shake hands with n – 1 other persons, giving the expression n(n – 1). We must correct this because it double counts handshakes, counting once for each source and again for each target. To fix the double counting we simply divide by 2, which yields n(n – 1) / 2.

My friend went another route, instead solving the problem in sequence: the first person must shake hands with n – 1 people. But the second person, since he/she has already shaken hands with the first person we already counted, has n – 2 people left. This process is repeated, giving a sum formula like so:

n  – 1 + n – 2 + n – 3 + …. + 1

You can easily verify that both formulas give them same result by testing for several values of n. Thus the sum formula should be reducible to n(n – 1) / 2. The trick to make this reduction is to group the terms of the sum formula into pairs that add to the same value. The pairing is done from the “outer extremes” and moving inward, for example with

n – 1 + n – 2 + n – 3 + …. + 3 + 2 + 1

we can make the following pairs

n – 1 + 1,  n – 2 + 2,  n – 3 + 3…

and note that each of these pairs add to n. Using a concrete example, with n = 5:

4 + 3 + 2 + 1 = (4 + 1) + (2 + 3)

there are (n – 1) / 2 pairs that each sum to n, which gives

(n – 1) / 2 * n = n(n – 1) / 2

If n is even, as for example with n=6:

5 + 4 + 3 + 2 + 1 = (5+0) + (4+1) + (3+2)

here there are n/2 pairs that each sum to n – 1:

(n – 1) * n/2 = n(n – 1) / 2

So the sum formula reduces to the original answer. Astute reads will have noticed that the sum formula is just the sum analog of the factorial operation. Values obtained from this sum formula are called triangle numbers, with notation Tn. Triangle numbers have a similar geometric interpretation to square numbers; adding the next value in the series is equivalent to adding an extra “layer” to the previous triangle: