Suppose there are 50 people at a party, and every person shakes hands with every other person at the party. How many distinct handshakes are there? (If you and I shake hands, that counts as one handshake only.)

I began this problem by thinking about each person individually. In order for every person to shake hands with every other person in the room, each person would have to make 49 handshakes. BUT! Since each handshake involves two people, we wouldn't count 49*50. There are at least two ways to reduce this number to an accurate count. Most directly, take only half of 49*50. i.e. H₅₀ = (49*50)/2. In general, H_n = (n-1)n/2.

Or, look again at each person and consider how many NEW handshakes each one makes. The first person will make 49 new handshakes. Person #2 will make 49 handshakes, but one of those is the one he already made with Person #1. Person #3 makes 49 handshakes, but one is from Person #1 and another is from Person #2. So, each person makes one less new handshake than the person before. In this case, our solution is the summation from 1 to 49, or in general: H_n =. This idea brings us right up to the recursive formula. If each new H_n is the summation up to one higher number, then H_n = H_n-1 + n-1.

The closed formula is a little bit trickier to justify, but we should recall the two other summation problems we have already done. In the lion problem, we summed from 1 to n-2 and had the closed formula: L_n = (n-1)(n-2)/2. In the triangular numbers problem, we summed from 1 to n and had the closed formula: T_n = n(n+1)/2.

Let's consider first the specific situation of H₅₀ and consider how its summation could be generalized.

As you can see, each pairing sums up to 50 (or n); and this occurs 24 times (or (n-2)/2, or (n/2) -1). Plus, there is an odd term left to add in: 25 (or n/2). So the summation could be described in general terms as H_n = n[(n/2) -1] +n/2.

Simplified:

= n²/2 - n + n/2
= n²/2 - 2n/2 + n/2
= (n² - 2n + n)/2
= (n² - n)/2
= n(n-1)/2

In these cases, a sequence with an odd number of terms can be generalized to the same closed formula as a sequence with an even number of terms, even though the process to arrive there is different. Since it is easier to consider the sequence with an even number of terms, let us consider only those for this discussion. Recall the three formulas we have discovered thus far.

= (n-1)(n-2)/2 (Lion Problem)

= n(n-1)/2 (Handshake Problem)

= (n+1)n/2 (Triangular Numbers)

Let me offer the following analysis of these formulas:
 

Other students in the class offered two other interesting approaches to finding the closed formula for the number of handshakes. One is more abstracted from the situation, the other is more abstracted in its formulation, but both are intriguing to consider:

Another Approach - part 1.

The handshake problem is a combinatoric problem where two people are chosen from a set of 50 each time. The familiar formula for this is  which is defined as . I can't follow the train of thought from our situation to the development of this formula, but I can show that it leads to the same closed formula that I developed.

= 

Another Approach - part 2.

Here we are trying to find another way to relate this summation to other summations we've considered. Recall that one alternative way of finding the triangular numbers was to consider n² and subtract the unnecessary dots, which turned out to be T_n-1. (i.e. T_n = n² - T_n-1). If you recall that T_n =  and T_n-1 = , then you can see that H_n = T_n-1. Or, in terms of n², it's like subtracting the T_n part instead of the T_n-1 part. So, H_n = n² - T_n. Or, in terms of n only, replace T_n with its closed formula and you get: H_n = n² - n(n+1)/2.

SUMMARY OF SOLUTIONS:

Numerical Solution
H₅₀ = 1225
Recursive Formula
H_n = H_n-1 + n-1
Closed Formula
H_n = n(n-1)/2