The main problem we solved in this recitation is the handshake problem. As we walk through the cases for n=1 and n=2, the idea to prove for general cases becomes clear. We conjecture that the hostess shakes hands with n-1 in a party of n couples.
First of all, we observed that the 2n-1 people other than the host shakes hands with 0, 1, \ldots, 2n-2 respectively. We call the person that doesn’t shake hands Alice and the one that shakes hands with 2n-2 people Bob. We showed that Alice and Bob are couple and they are not the host and the hostess. If we temporarily remove Alice and Bob from the party, the rest of the people consist a smaller party satisfying the conditions in the problem. So by induction hypothesis, the hostess in the smaller party of n-1 couples shakes hands with n-2. However, if we put Alice and Bob back to the party, the hostess shakes hands with one extra person, Bob. Hence, originally, the hostess shakes hands with n-1 people. This finishes the induction step.
It’s interesting that the number of handshakes with the host is equal to the one with the hostess. This was raised by one of the students in section D. And it also can be done by a proof of induction.