Every arriving guest shakes hand with everybody else at a party. If there are n guests in the party, how many handshakes were there? Proof by using induction.
My approach to this problem was to write down a list of values for n and the corresponding people shaking hands. For instance, for n = 4, let's say A shakes hand with B, C, and D; B shakes hand with C and D; and C shakes hand with D.
Is the approach correct?
+---------+----------------------------------------------------+ | n | Number of handshakes | +---------+----------------------------------------------------+ | 1 | Zero | | 2 | One | | 3 | A shakes hand with B and C; B shakes hand with C | | | Therefore, 3 = 2 + 1 | | 4 | A shakes hand with B, C, and D; | | | B shakes hand with C and D; | | | C shakes hand with D; | | | Therefore, 6 = 3 + 2 + 1 | | k | (k-1) + (k-2) + ... + 2 + 1 | | k+1 | k + (k-1) + ... + 2 + 1 | +---------+----------------------------------------------------+
What should I do next?
Best Answer
Your approach is correct.
The first person to arrive has no one with whom to shake hands. The second person to arrive can shake hands with the one person already present. The third person to arrive can shake hands with the two people already present. In general, the $k$th person to arrive can shake hands with the $k - 1$ people already present. Thus, if there are $n$ people present at the party, the number of handshakes is $$\sum_{k = 1}^{n} (k - 1) = \sum_{k = 0}^{n - 1} k = \frac{n(n - 1)}{2}$$ as you observed in the comments.
Inductive Proof: Let $P(n)$ be the statement that if $n$ people are present at the party and each person shakes the hand of every other person at the party, then the number of handshakes is $\frac{n(n - 1)}{2}$.
Let $n = 1$. Since the first person has no one with whom to shake hands, no handshakes occur. Since $$\frac{1(1 - 1)}{2} = \frac{1 \cdot 0}{2} = 0$$ $P(1)$ holds.
Thus, we may assume $P(m)$ holds for some positive integer $m$.
Let $n = m + 1$. When the $(m + 1)$st person arrives at the party, the number of handshakes that have already occurred is, by hypothesis, $$\frac{m(m - 1)}{2}$$ The new guest then shakes the hands of each of the $m$ people present, after which every person has shaken the hand of each of the other people at the party and the number of handshakes that have occurred is $$\frac{m(m - 1)}{2} + m = m\left[\frac{m - 1}{2} + 1\right] = m\left[\frac{m - 1}{2} + \frac{2}{2}\right] = \frac{m(m + 1)}{2}$$ so $P(m) \Rightarrow P(m + 1)$.
Since $P(1)$ holds and $P(m) \Rightarrow P(m + 1)$ for each positive integer $m$, $P(n)$ holds for each positive integer $n$.
Combinatorial Proof: The number of handshakes is equal to the number of ways that two of the $n$ people present can be paired, which is $$\binom{n}{2} = \frac{n!}{2!(n - 2)!} = \frac{n(n - 1)(n - 2)!}{2(n - 2)!} = \frac{n(n - 1)}{2}$$
Combinatorial Proof: The number of handshakes is equal to the number of subsets consisting of two of the $n$ people present at the party. We can count these subsets by adding up the number of handshakes performed by each person as she or he arrives at the party. Since the $k$th person to arrive at the party shakes the hand of the $k - 1$ people already present, we may conclude that the number of handshakes that occur when $n$ people are present at the party is $$\binom{n}{2} = \sum_{k = 1}^{n} (k - 1) = \sum_{k = 0}^{n - 1} k = \frac{n(n - 1)}{2}$$ A variation of this argument was used by al-Banna to derive the formula for $\binom{n}{2}$.